Leetcode 19. Remove Nth Node From End of List JAVA语言

1

2

3

4

5

6

7

8

<code>Given a linked list, remove the nth node from the end of list and return its head.</code>

<code>For example,</code>

<code>   </code><code>Given linked list: 1-&gt;2-&gt;3-&gt;4-&gt;5, and n = 2.</code>

<code>   </code><code>After removing the second node from the end, the linked list becomes 1-&gt;2-&gt;3-&gt;5.</code>

<code>Note:</code>

<code>Given n will always be valid.</code>

<code>Try to do this in one pass.</code>

题意：删除倒数第N个节点。尽量一次遍历。

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

<code>/**</code>

<code> </code><code>* Definition for singly-linked list.</code>

<code> </code><code>* public class ListNode {</code>

<code> </code><code>*     int val;</code>

<code> </code><code>*     ListNode next;</code>

<code> </code><code>*     ListNode(int x) { val = x; }</code>

<code> </code><code>* }</code>

<code> </code><code>*/</code>

<code>public</code> <code>class</code> <code>Solution {</code>

<code>    </code><code>public</code> <code>ListNode removeNthFromEnd(ListNode head, </code><code>int</code> <code>n) {</code>

<code>        </code><code>if</code><code>(head==</code><code>null</code> <code>|| n&lt;</code><code>1</code><code>)</code><code>return</code> <code>head;</code>

<code>        </code><code>ListNode cur=head;</code>

<code>        </code><code>while</code><code>(cur!=</code><code>null</code><code>){</code>

<code>            </code><code>n--;</code>

<code>            </code><code>cur=cur.next;</code>

<code>        </code><code>}</code>

<code>        </code><code>if</code><code>(n==</code><code>0</code><code>)head=head.next;</code>

<code>        </code><code>if</code><code>(n&lt;</code><code>0</code><code>){</code>

<code>            </code><code>cur=head;</code>

<code>            </code><code>while</code><code>(++n!=</code><code>0</code><code>){</code>

<code>                </code><code>cur=cur.next;</code>

<code>            </code><code>}</code>

<code>            </code><code>cur.next=cur.next.next;</code>

<code>        </code><code>return</code> <code>head;</code>

<code>        </code> 

<code>    </code><code>}</code>

<code>}</code>

PS:左老师提供的一种找倒数第K个的思路。先遍历一遍，同时K--，最后判断K的大小。K==0说明要删除的是头结点。K&gt;0，说明K不对。K&lt;0的时候，再从头走一遍，不过此时K++，K=0的时候也就找到了第K-1个。此时直接删除就行。

【方法2】网上的快慢指针法。fast先走K-1步。然后slow和fast同时一步一步走。fast到尾部时slow正好到达倒数第K-1个。

29

30

31

<code>/*</code>

<code>public class ListNode {</code>

<code>    </code><code>int val;</code>

<code>    </code><code>ListNode next = null;</code>

<code> </code> 

<code>    </code><code>ListNode(int val) {</code>

<code>        </code><code>this.val = val;</code>

<code>}*/</code>

<code>    </code><code>public</code> <code>ListNode FindKthToTail(ListNode head,</code><code>int</code> <code>k) {</code>

<code>        </code><code>if</code><code>(head==</code><code>null</code> <code>|| k==</code><code>0</code><code>)</code><code>return</code> <code>null</code><code>;</code>

<code>        </code><code>ListNode fast=head;</code>

<code>        </code><code>for</code><code>(</code><code>int</code> <code>i=</code><code>0</code><code>;i&lt;k-</code><code>1</code><code>;i++){</code>

<code>            </code><code>////防止K无效</code>

<code>            </code><code>if</code><code>(fast.next!=</code><code>null</code><code>){</code>

<code>                </code><code>fast=fast.next;   </code>

<code>            </code><code>}</code><code>else</code><code>{</code>

<code>                </code><code>return</code> <code>null</code><code>;</code>

<code>             </code> 

<code>        </code><code>ListNode slow=head;</code>

<code>        </code><code>while</code><code>(fast.next!=</code><code>null</code><code>){</code>

<code>            </code><code>slow=slow.next;</code>

<code>            </code><code>fast=fast.next;</code>

<code>        </code><code>return</code> <code>slow;</code>

本文转自 努力的C 51CTO博客，原文链接:http://blog.51cto.com/fulin0532/1905464