链表双指针技巧

1合并两个有序链表

  • 思路：两个链表各有一个指针p1，p2

    while循环每次比较p1和p2的大小，把较小的节点链接到结果链表上

  • 伪代码

    1
    2
    3
    4
    5
    6
    7
    8
    while (...){
        if (p1->val > p2->val){
            p->next = p2;
            p2 = p2->next;
        }
        else..
        p = p->next;
    }

  • 示意图：
    //初始
    p1
    1->3->5->7
    p2
    2->4->6->8

    //第一次循环
    p
    -1->1->3->5->7
    p1
    3->5->7
    p
    1->3->5->7

    //第二次循环
    p
    1->2->4->6->8
    p2
    4->6->8

2单链表的分解

  • 思路：同两个链表的合并，while循环每次比较原链表和x的大小

    分解成一个元素大小小于x的small链表，和另一个large链表，然后把两个链表接在一起

  • 伪代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    哨兵节点small链表
    哨兵节点large链表
    while（遍历原链表）{
        if head元素<x{
            该元素接到small链表
            双指针移动
        }
        原指针移动
    }
    small尾接large头
    large尾置空

3合并k个有序链表

  • 思路：优先级队列（二叉堆）
  • 伪代码：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    声明优先级队列
    k个头节点放入堆
    哨兵节点
    while 遍历堆{
        取出最小元素（堆头）放入结果链表
        结果指针移动
        将堆的下一个节点放入堆
    }

  • 真代码，语法完全不熟练
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    class Solution {
    public:
        struct Status {
            int val;
            ListNode *ptr;
            bool operator < (const Status &rhs) const {
                return val > rhs.val;
            }
        };

        priority_queue <Status> q;

        ListNode* mergeKLists(vector<ListNode*>& lists) {
            for (auto node: lists) {
                if (node) q.push({node->val, node});
            }
            ListNode head, *tail = &head;
            while (!q.empty()) {
                auto f = q.top(); q.pop();
                tail->next = f.ptr; 
                tail = tail->next;
                if (f.ptr->next) q.push({f.ptr->next->val, f.ptr->next});
            }
            return head.next;
        }
    };

4单链表的倒数第k个节点

  • 思路：
    - 白菜思路：找第n-k+1个节点。但n其实是未知的，还需要一次遍历。
    - sp思路：p1指针走k步，然后p1和p2指针同时走，p1走到末尾时p2的位置即为所求

  • 伪代码：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    初始化p1指针
    for k次{
      p1移动
    }
    初始化p2指针
    while p1不为空{
      p1移动
      p2移动
    }

5单链表的中点

  • 思路:快慢指针
  • 伪代码
    1
    2
    3
    4
    while 快指针和快指针的next不为空{
        慢走1
        快走2
    }

6判定链表包含环

  • 思路：快慢指针，相遇→有环，快指针置空→无环
  • 伪代码：
    1
    2
    3
    4
    ...
    if slow==fast{
        return true;
    }
  • 环起点思路：相遇后，任一指针回到head，同一速度再次相遇，即为起点

7判定链表相交

  • 思路：p1遍历完链表A之后开始遍历链表B，让p2遍历完链表B之后开始遍历链表A，这样相当于「逻辑上」两条链表接在了一起。
  • 伪代码
    1
    2
    3
    4
    5
    6
    7
    while p1!=p2{
        if p1为空 p1指向b链表
        else 移动
        if p2为空 p2指向a链表
        else 移动
        //相遇时p1=p2即为交点，都为空则不相交
    }