前端程式員學好演算法系列（四）鏈表

24. 兩兩交換鏈表中的節點
給定一個鏈表，兩兩交換其中相鄰的節點，並返回交換後的鏈表。

你不能只是單純的改變節點內部的值，而是需要實際的進行節點交換。

示例:

給定 1->2->3->4, 你應該返回 2->1->4->3.

解題：我們定義4個指針如上進行節點交換，
1.給head添加一個虛擬頭節點thead
2.定義4個指針 p， node1， node2， next 我們需要將p.next ->node2  node1.next -> next    node2.next ->node1        完成以後將 p指針移動到node1
3.我們需要判斷 p.next 和p.next.next 都不為空，這樣next 最差為null 不會越界

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
    let thead = new ListNode(0);
    thead.next = head;
    let p = thead;
    while(p.next != null && p.next.next != null){
        let node1 = p.next;
        let node2 = node1.next;
        let next = node2.next

        p.next = node2;
        node1.next = next;
        node2.next = node1;
        p = node1;
    }
    return thead.next;
};

237. 刪除鏈表中的節點
請編寫一個函數，使其可以刪除某個鏈表中給定的（非末尾）節點，你將只被給定要求被刪除的節點。

現有一個鏈表 -- head = [4,5,1,9]，它可以表示為:

示例 1:

輸入: head = [4,5,1,9], node = 5
輸出: [4,1,9]
解釋: 給定你鏈表中值為 5 的第二個節點，那麼在調用了你的函數之後，該鏈表應變為 4 -> 1 -> 9.

解題：

1.我們無法直接刪除給定的節點，我們只能拿到給定節點的下一個節點的值，

2.我們用該節點的下一個節點的值覆蓋當前節點的值，然後刪除下一個節點，即相當於實現了對該節點的刪除

3.我們處理node 為null和node.next為null的特殊情況

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} node
 * @return {void} Do not return anything, modify node in-place instead.
 */
var deleteNode = function(node) {
     if(node == null){
        return
     }
     if(node.next == null){
          delete node
          node = null
          return
     }
     node.val = node.next.val
     node.next = node.next.next
};

19. 刪除鏈表的倒數第N個節點
給定一個鏈表，刪除鏈表的倒數第 n 個節點，並且返回鏈表的頭結點。

示例：

給定一個鏈表: 1->2->3->4->5, 和 n = 2.

當刪除了倒數第二個節點後，鏈表變為 1->2->3->5.

解題：
1.給head設置虛擬頭節點
2.設置fast 和show兩個指針
3.fast指針先移動n位，然後fast指針和show指針同時移動
4.當fast指針為空時，show.next節點即為需要刪除的節點，我們把show.next ->show.next.next

/**
 * 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) {
    let preHead = new ListNode(0)
    preHead.next = head
    let fast = preHead, slow = preHead
    // 快先走 n+1 步
    while(n--) {
        fast = fast.next
    }
    let i = 0
    // fast、slow 一起前進
    while(fast && fast.next) {
        slow = slow.next
        fast = fast.next
        
    }
    slow.next = slow.next.next
    return preHead.next
};

鏈表的js演算法就先介紹到這裡了