LeetCode--019--删除链表的倒数第N个节点(java)

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

用两个节点fast和slow，先让fast走n步，然后slow和fast一起走，等fast走到最后一个节点时，slow所在位置就是要删除的前一个节点。其他注意的就是抠边界了。

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) { val = x; }
 7  * }
 8  */
 9 class Solution {
10     public ListNode removeNthFromEnd(ListNode head, int n) {
11         ListNode fast = head,slow = head;
12         
13         while(n > 0){
14             n--;
15             fast = fast.next;
16         }
17         while(fast!=null && fast.next!=null){
18             fast = fast.next;
19             slow = slow.next;
20         }
21         if(fast == null){//fast为空有两种情形1.[1] n = 1   2.[1,2,3,4] n = 4分别对应下面的else 和 if
22             if(head != null && head.next!=null){
23                 head = head.next;
24                 return head;
25             }else{
26                 head = null;
27                 return head;
28             }
29             
30         }
31             fast = slow.next;
32             slow.next = fast.next;
33         return head;
34     }
35 }

2019-04-17 21:59:17

双指针python版本

 1 class Solution:
 2     def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
 3         q1 = ListNode(-1)
 4         q2 = ListNode(-1)
 5         q1=head
 6         q2=head
 7         i = n
 8         while i>0:
 9             q1=q1.next
10             i-=1
11         if n==1 and q1==None:  #只有一个节点的情况
12             return q1
13         elif q1==None:#删除第一个节点的情况
14             return head.next
15         while q1.next!=None: #其他情况
16             q1 = q1.next
17             q2 = q2.next
18         q2.next =q2.next.next
19         return head

2019-11-30 09:18:02

递归版：

 1 class Solution:
 2     def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
 3         def help(node):
 4             if not node:
 5                 return 0
 6             i = help(node.next)+1
 7             if i>n:
 8                 node.next.val=node.val
 9             return i
10         help(head)
11         return head.next