LeetCode 7. Reverse Integer

題目

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, n = 2.

   從後面數2個,移除4後的連結陣列變成 1->2->3->5.
注意:

n不會比連結陣列還長,試著跑一次迴圈解題。

思路

這題可以用快慢指針的做法,就是快指針先走n個節點,慢指針再開始與快指針一起跑,當快指針到底的時候,慢指針會停在要移除的節點n上面。

不過慢指針應該要停在要移除節點的前一點才對,因為連結陣列的刪除,應該是前一點跳過下一點,這樣當前的節點就會被刪除。 因此將慢指針的起點改在一個假的首節點0上面修正這個問題。

解題

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
    if(head == null) return head; 

    // 用假節點當首節點,方便操作
    var node = new ListNode(0);
    node.next = head;


    var slow = node;
    var fast = head;

    // 快指針先跑n個節點
    while(n > 0){
        fast = fast.next;
        n--;
    }

    // 因為快指針已經先跑n點,所以當快指針fast跑完,慢指針slow會在要移除的前一點上
    while(fast){
        fast = fast.next;
        slow = slow.next;
    }
    if(slow.next == null){
        slow.next = null ;
    } else {
        slow.next = slow.next.next;
    }

    return node.next;
};
  • [1,2,3,4] , n = 2,fast = [1,2,3,4] , slow = [0,1,2,3,4] (0為假節點)
  • n = 2,快指針先走2點,fast = [3,4],slow = [0,1,2,3,4]
  • 快慢指針一起跑,當fast = null,slow = [2,3,4],這時候慢指針必須跳過他第2個點,也就是跳過3

results matching ""

    No results matching ""