链表训练

链表 (opens new window)

1.反转链表 (opens new window)

• 迭代：

var reverseList = function(head) {
    let prev = null;
    let curr = head;
    while (curr) {
        const next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
};

• 递归：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
  if (!head || !head.next) return head;
  
  let last = reverseList(next);
  head.next.next = head;
  head.next = null;

  return last;
}

// 怎么理解递归操作？
function reverse1(head) {
  // 1.递归结束判断，只剩一个节点
  if(!head || !head.next) return head

  // 2.递归把head.next之后的反转：head -> reversedHead
  let newHead = reverseList(head.next)

  let oldHead = head
  // 原来：oldHead -> (未反转部分 a->b->c, oldHead.next == a, c.next == oldLast)-> (oldLast = null)
  // reverseList(head.next)操作之后：oldHead -> (已反转部分 a<-b-<c, oldHead.next == a, c.next == b, a.next == oldLast)-> (oldLast = null)
  let oldLast = oldHead.next.next
  // 3.反转head和reverseList(head.next)
  oldHead.next.next = oldHead
  oldHead.next = oldLast

  return newHead
}

// 实现reverseN,反转链表前n个
function reverseN(head, n) {
  // 递归终点
  if(!head || !head.next || n <= 1) return head

  // 递归head.next
  let newHead = reverseN(head, n - 1)

  let oldHead = head
  let oldLast = oldHead.next.next

  // 反转head
  oldHead.next.next = oldHead
  oldHead.next = oldLast

  return newHead
}

2.反转链表 II (opens new window)

• 迭代解法 (opens new window)

var reverseBetween = function(head, left, right) {
    // 使用dummy节点，可以避免过多的判断
    //     -1 -> 1 -> 2 -> 3 -> 4
    // dummy -> a -> b -> c -> d
    const dummy_node = new ListNode(-1);
    dummy_node.next = head;
    let pre = dummy_node;
    // 找到left的前一个节点
    for (let i = 0; i < left - 1; ++i) {
        pre = pre.next;
    }

    // [left = 2, right = 4]之间开始反转
    //    -1 -> 1 -> 2 -> 3 -> 4
    // dummy -> a -> b -> c -> d
    // pre即left前一个结点，cur即left当前的节点
    // 头插法，即将cur下一个节点插入到cur之前pre之后
    let cur = pre.next
    for(let i=0; i<right - left; i++) {
        // 将cur的下一个节点放到pre之后
        // 1.断开cur下一个节点
        let removed = cur.next
        cur.next = removed.next
        // 2.将cur下一个节点插入到pre后面
        removed.next = pre.next
        pre.next = removed
    }
    return dummy_node.next;
};

• 递归解法 (opens new window)

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function reverseBetween(head: ListNode | null, left: number, right: number): ListNode | null {
  if (!head || !head.next) return head

  if (left === 1) {
    return reverseN(head, right)
  }

  head.next = reverseBetween(head.next, left - 1, right - 1)

  return head
};

// 反转链表前 N 个节点
function reverseN(head: ListNode | null, n: number): ListNode | null {
  if (!head || !head.next) return head

  if (n === 1) {
    return head
  }

  const last = reverseN(head.next, n - 1)

  let suc = head.next.next
  head.next.next = head
  head.next = suc

  return last
}

3.旋转链表 (opens new window)

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]

• 每次将最后一个节点放到最前面，循环k次

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var rotateRight = function(head, k) {
    let len = 0
    let p = head
    while(p) {
        p = p.next
        len++
    }

    let cur = head
    k = k % len
    for(let i=0; i<k; i++) {
        cur = moveLastToHead(cur)
    }

    return cur
};

function moveLastToHead(head) {
    if(!head || !head.next) return head

    let lastTwo = head.next
    while(lastTwo.next) {
      lastTwo = lastTwo.next
    }

    let last = lastTwo.next
    lastTwo.next = null
    last.next = head

    return last
}

• 先获取倒数第k+1个元素， 然后将链表成环， 倒数第k处断开环， 倒数第k个元素即为新的头结点

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function rotateRight(head: ListNode | null, k: number): ListNode | null {
    if(!head || !head.next) return head

    // 1.获取链表长度
    let len = getLength(head)
    // 优化k
    k = k % len
    // 2.获取倒数第k+1个元素
    let pre = getLastK(head, k + 1)

    // 3.成环
    // 3.1 获取最后一个元素
    let last = getLastK(pre, 1)
    // 3.2 尾首联接
    last.next = head

    // 4.断开环
    let newHead = pre.next
    pre.next = null

    return newHead
};

function getLength(head: ListNode | null): number {
    let n = 0
    while(head) {
        head = head.next
        n++
    }
    return n
}

function getLastK(head: ListNode | null, k: number): ListNode | null {
    if(!head || !head.next) return head

    let p1 = head, p2 = head

    // p1先走k步
    for(let i=0; i<k; i++) {
        p1 = p1.next
    }
    // p1, p2同时前进，直至p1到达尾部
    while(p1) {
        p1 = p1.next
        p2 = p2.next
    }
    return p2
}

4.合并两个有序链表 (opens new window)

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

输入：l1 = [], l2 = [0]
输出：[0]

• 迭代法

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function (list1, list2) {
  if (list1 === null) return list2;
  if (list2 === null) return list1;

  let p = new ListNode(-1)
  pre = p
  let p1 = list1
  let p2 = list2
  while (p1 && p2) {
    if (p1.val < p2.val) {
      p.next = p1
      p1 = p1.next
    } else {
      p.next = p2
      p2 = p2.next
    }

    // 断开
    let temp = p.next
    temp.next = null
    p = temp
  }

  if (p1) {
    p.next = p1
  }

  if (p2) {
    p.next = p2
  }

  return pre.next
};

• 递归法

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function(list1, list2) {
    if(!list1) return list2
    if(!list2) return list1

    if(list1.val < list2.val) {
        list1.next = mergeTwoLists(list1.next, list2)
        return list1
    } else {
        list2.next = mergeTwoLists(list1, list2.next)
        return list2
    }
};

5.合并k个升序链表 (opens new window)

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function (lists) {
  // 多个 -> 2 个
  return merge(lists, 0, lists.length - 1)
};

function merge(lists, left, right) {
  if (left === right) return lists[left]
  if (left > right) return null
  let mid = (left + right) >> 1
  return mergeTwo(merge(lists, left, mid), merge(lists, mid + 1, right))
}

// 将两个升序链表合二为一
function mergeTwo(list1, list2) {
  let p = new ListNode(-1)
  let dummy = p

  let p1 = list1
  let p2 = list2

  while (p1 && p2) {
    if (p1.val < p2.val) {
      p.next = p1
      p1 = p1.next
    } else {
      p.next = p2
      p2 = p2.next
    }
    
    // 断开
    let temp = p.next
    temp.next = null
    p = p.next
  }

  // 剩余的补上
  p.next = p1 ? p1 : p2

  return dummy.next
}

6.环形链表 (opens new window)

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    if(!head || !head.next) return false;
    
    let slow = head, fast = head;
    
    while(fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        
        if(slow === fatse) return true;
    }
    
    return false;
}

7.环形链表 II (opens new window)

给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function (head) {
  if (!head || !head.next) return null

  let slow = head, fast = head

  // 先走到相遇点
  while (fast && fast.next) {
    slow = slow.next
    fast = fast.next.next

    // 相遇了
    if (slow === fast) break
  }

  // 判断一下是否有环
  if (!fast || !fast.next) return null

  // 此时 slow和fast都在第一相遇点
  // 【起点】 --相距x--> 【环入口点】 ---> 【相遇点】 --相距为y-> 【环入口点】
  // x === y
  let p1 = head // 从起点开始
  let p2 = slow // 从相遇点开始

  // 相同速度直至相遇：环入口点
  while (p1 !== p2) {
    p1 = p1.next
    p2 = p2.next
  }

  return p1
};

8.两个链表的第一个公共节点 (opens new window)

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
    if(!headA || !headB) return null;

    var n1 = headA;
    var n2 = headB;
    while(n1 != n2) {
        n1 = n1 == null ? headB : n1.next;
        n2 = n2 == null ? headA : n2.next;
    }

    return n1;

};

9.K个一组翻转链表 (opens new window)

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var reverseKGroup = function(head, k) {
    let a = head, b = head;
    
    // 先找到第一组k的分界节点
    for(let i=0; i<k; i++) {
        if(b===null) return head;
        b = b.next;
    }
    // 翻转head和分界节点之间的节点b（翻转链表）
    const newHead = reverse(a, b);
    // 继续翻转b之后的节点
    a.next = reverseGroup(b, k);
    return newHead;
}

// 翻转a,b节点之间的节点
function reverse(a, b) {
    let prev = null, cur = a, next;
    
    while(cur !== b) {
        next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }
    
    return prev;
}

10.排序链表 (opens new window)

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function(head) {
    if (head == null) return null;
    let newHead = head;
    return mergeSort(head);
};
function mergeSort(head) {
    if (head.next != null) {
        let slower = getCenter(head);
        let nxt = slower.next;
        slower.next = null;
        const left = mergeSort(head);
        const right = mergeSort(nxt);
        head = merge(left, right);
    }
    return head;
}
function merge(left, right) {
    let newHead = null, head = null;
    while (left != null && right != null) {
        if (left.val < right.val) {
            if (!head) {
                newHead = left;
                head = left;
            } else {
                newHead.next = left;
                newHead = newHead.next;
            }
            left = left.next;
        } else {
            if (!head) {
                newHead = right;
                head = right;
            } else {
                newHead.next = right;
                newHead = newHead.next;
            }
            right = right.next;
        }
    }
    newHead.next = left ? left : right;
    return head;
}
function getCenter(head) {
    let slower = head, faster = head.next;
    while (faster != null && faster.next != null) {
        slower = slower.next;
        faster = faster.next.next;
    }
    return slower;
}

11.相交链表 (opens new window)

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
    if(!headA || !headB) return null;
    
    let a = headA, b = headB;
    
    while(a !== b) {
       a = a === null ? headB : a.next;
       b = b === null ? headA : b.next;
    }
    
    return a;
};

12.回文链表 (opens new window)

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

输入：head = [1,2,2,1]
输出：true

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function(head) {
  if(head === null || head.next === null) return true;
  // 1.获取中间节点
  // 1 -> 2 -> 2 -> 1 mid取3
  // 1 -> 2 -> 3 -> 2 -> 1 mid取3
  let midHead = getMidNode(head);
  // 2.反转mid之后的链表
  let reservedMid = reverseList(midHead);
  
  // 由于反转前后链表并没有断开：
  // 1 -> 2 -> 2 <- 1
  // 1 -> 2 -> 3 <- 2 <- 1
  // 我们需要反转的是后面的部分，如果断开了，就需要判断链表的奇偶了
  
  // 3.判断mid点后对称位置是否值一样
  while(reservedMid !== null) {
    // 如果断开了，没处理奇偶长度，此时head可能为null
    if(head.val !== reservedMid.val) {
      return false;
    }
    head = head.next;
    reservedMid = reservedMid.next;
  }
  return true;
};

var reverseList = function(head) {
  if(head === null || head.next === null) return head;
  let reversedNext = reverseList(head.next);
  head.next.next = head;
  head.next = null;
  return reversedNext;
}

var getMidNode = function(head) {
  let slow = head;
  let fast = head;
  while(fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
  }
  
  // 判断奇偶
  // if(fast) {
    // 链表奇数长度
    // return slow.next
  // }
  
  return slow;
}