[算法]链表中双指针

交叉

剑指 Offer 52. 两个链表的第一个公共节点(160. 相交链表)

双指针

var getIntersectionNode = function(headA, headB) {
    let p1 = headA, p2 = headB;
    while (p1 != p2) {
        p1 = p1 == null ? headB : p1.next;
        p2 = p2 == null ? headA : p2.next;
    }
    return p1;
};

328. 奇偶链表

function oddEvenList(head: ListNode | null): ListNode | null {
    if (head == null) return head;
    let odd: ListNode = head, even: ListNode = head.next;
    let evenHead = even;
    while (even != null && even.next != null) {
        odd.next = even.next;
        odd = odd.next;
        even.next = odd.next;
        even = even.next;
    }
    odd.next = evenHead;
    return head;
};

快慢指针

876. 链表的中间结点（最简单的例子）

function middleNode(head: ListNode | null): ListNode | null {
    let fast = head, slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
};

剑指 Offer 22. 链表中倒数第k个节点（面试题 02.02. 返回倒数第 k 个节点）

双指针，第一个指针先找到正序的第k个结点，两个指针之间相差k个位置，然后两个指针同时后移，当快指针达到链表尾部时，慢指针就是倒数第k个结点

var getKthFromEnd = function(head, k) {
    let fast = head;
    let slow = head;
    // 快指针先行k步
    for (let i = 0; i < k; i++) {
        fast = fast.next
    }
    // 快慢指针同步移动， 直到快指针到尾部
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
};

203. 移除链表元素（剑指 Offer 18. 删除链表的节点）

距离为一快慢指针+哨兵节点

var removeElements = function(head, val) {
    let dummyHead = new ListNode(0);
    dummyHead.next = head;
    let slow = dummyHead;
    let fast = head;
    while (fast != null) {
        if (fast.val == val) {
            slow.next = fast.next;
        } else {
            slow = fast;
        }
        fast = fast.next
    }
    return dummyHead.next;
};

19. 删除链表的倒数第 N 个结点 （完成版， 肯能删除第一个节点）

快慢指针 + dummy

var removeNthFromEnd = function(head, n) {
    let dummy = new ListNode(0, head); // 处理若删除第一个的情况
    let fast = dummy, slow = dummy;
    for (let i=0; i<=n; i++) { // 注意边界线， 移动n+1个位置
        fast = fast.next;
    }
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;
    return dummy.next;
};

扩展： 1721. 交换链表中的节点

思想： 交换节点， 交换指针的val, 无需移动next

var swapNodes = function(head, k) {
    let fast = head;
    let slow = head;
    let firstNode;
    for (let i=0; i<k; i++) {
        if (i == k - 1) { // 易错点
            firstNode = fast
        }
        fast = fast.next;
    }
    console.log(firstNode.val)
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }
    // 注意， [firstNode.val, slow.val] = [slow.val, firstNode.val] 写法错误
    let tmp = firstNode.val;
    firstNode.val = slow.val;
    slow.val = tmp;
    return head;
};

面试题 02.01. 移除重复节点

var removeDuplicateNodes = function(head) {
    if (head == null || head.next == null) return head;
    const cache = new Set([]);
    cache.add(head.val);
    let cur = head, fast = head.next;
    while (fast !== null) {
        if (!cache.has(fast.val)) {
            cur.next = fast;
            cur = cur.next;
            cache.add(fast.val);
        }
        fast = fast.next;
    }
    cur.next = null;
    return head;
};

61. 旋转链表

function rotateRight(head: ListNode | null, k: number): ListNode | null {
    if (k == 0  || head == null || head.next == null) return head;
    // mod n
    let n = 0;
    let p = head;
    while (p != null) {
        ++n;
        p = p.next;
    }
    k %= n;
    if (k == 0) return head;

    let fast = head, slow = head;
    for (let i = 0; i < k; ++i) {
        fast = fast.next;
    }
    while (fast.next != null) {
        slow = slow.next;
        fast = fast.next;
    }
    let start = slow.next;
    slow.next = null;
    fast.next = head;
    return start;
};

143. 重排链表

快慢指针 + 翻转链表

/**
 * 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)
 *     }
 * }
 */

/**
 Do not return anything, modify head in-place instead.
 */
function reorderList(head: ListNode | null): void {
    if (head == null || head.next == null) return;
    let slow = head, fast = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }

    let cur = slow.next;
    slow.next = null;
    let pre = null;
    while (cur != null) {
        let t = cur.next;
        cur.next = pre;
        pre = cur;
        cur = t;
    }
    cur = head;
    while (pre != null) {
        let t = pre.next;
        pre.next = cur.next;
        cur.next = pre;
        cur = pre.next;
        pre = t;
    }
};