|
1
2
3
4
5
6
7
8
|
Given a linked list, remove the nth node from the end of list and return its head.For example, Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:Given n will always be valid.Try to do this in one pass. |
题意：删除倒数第N个节点。尽量一次遍历。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
/** * Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
if(head==null || n<1)return head;
ListNode cur=head;
while(cur!=null){
n--;
cur=cur.next;
}
if(n==0)head=head.next;
if(n<0){
cur=head;
while(++n!=0){
cur=cur.next;
}
cur.next=cur.next.next;
}
return head;
}
} |
PS:左老师提供的一种找倒数第K个的思路。先遍历一遍，同时K--，最后判断K的大小。K==0说明要删除的是头结点。K>0，说明K不对。K<0的时候，再从头走一遍，不过此时K++，K=0的时候也就找到了第K-1个。此时直接删除就行。
【方法2】网上的快慢指针法。fast先走K-1步。然后slow和fast同时一步一步走。fast到尾部时slow正好到达倒数第K-1个。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
/*public class ListNode { int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(head==null || k==0)return null;
ListNode fast=head;
for(int i=0;i<k-1;i++){
////防止K无效
if(fast.next!=null){
fast=fast.next;
}else{
return null;
}
}
ListNode slow=head;
while(fast.next!=null){
slow=slow.next;
fast=fast.next;
}
return slow;
}
} |
本文转自 努力的C 51CTO博客，原文链接:http://blog.51cto.com/fulin0532/1905464