[leetcode]19. Remove Nth Node From End of List删除链表倒数第N个节点

Given a linked list, remove the n-th node from the end of list and return its head.

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.

Follow up:

Could you do this in one pass?

题意：删除链表倒数第N个节点

Solution1: Two Pointers(fast and slow)

1. Let fast pointer to move n steps in advance, making sure there is n steps gap between fast and slow

2. Move fast and slow pointer together until fast.next == null

code

 /**

  * Definition for singly-linked list.

  * public class ListNode {

  *     int val;

  *     ListNode next;

  *     ListNode(int x) { val = x; }

  * }

  */

 /*

 Time: O(n)

 Space: O(1)

 */

 class Solution {

       public ListNode removeNthFromEnd(ListNode head, int n) {

         ListNode dummy = new ListNode(-1);

         dummy.next = head;

         ListNode slow = dummy, fast = dummy;

         for (int i = 0; i < n; i++)  // fast先走n步

             fast = fast.next;

         while(fast.next != null) { // fast和slow一起走

             slow = slow.next;

             fast = fast.next;

         }

         //直接skip要删除的节点

         slow.next = slow.next.next;  // 思考为何不能写成 slow.next = fast;

         return dummy.next;

     }

 }

巴特西

[leetcode]19. Remove Nth Node From End of List删除链表倒数第N个节点

最新文章

热门文章