链表常用操作总结

1
2
3
4
5

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

1
2
3
4

ListNode* dummy = new ListNode(0);
dummy->next = head;
// ... 操作 ...
return dummy->next;

1
2
3
4
5
6
7
8

int getLength(ListNode* head) {
    int len = 0;
    while (head) {
        len++;
        head = head->next;
    }
    return len;
}

1
2
3
4
5
6

ListNode* findKth(ListNode* head, int k) {
    for (int i = 0; i < k - 1; i++) {
        head = head->next;
    }
    return head;
}

1
2
3
4
5
6
7
8
9

ListNode* getKthFromEnd(ListNode* head, int k) {
    ListNode *fast = head, *slow = head;
    for (int i = 0; i < k; i++) fast = fast->next;
    while (fast) {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

1
2
3
4
5
6
7
8

ListNode* middleNode(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

ListNode* reverseList(ListNode* head) {
    ListNode* pre = nullptr;
    ListNode* cur = head;
    while (cur) {
        ListNode* next = cur->next;  // 保存下一个
        cur->next = pre;             // 反转指针
        pre = cur;                   // pre 前进
        cur = next;                  // cur 前进
    }
    return pre;
}

1
2
3
4
5
6
7

ListNode* reverseList(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode* last = reverseList(head->next);
    head->next->next = head;
    head->next = nullptr;
    return last;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

ListNode* reverseBetween(ListNode* head, int left, int right) {
    ListNode* dummy = new ListNode(0);
    dummy->next = head;

    // 找到反转起点的前一个
    ListNode* pre = dummy;
    for (int i = 0; i < left - 1; i++) pre = pre->next;

    // 头插法反转
    ListNode* cur = pre->next;
    for (int i = 0; i < right - left; i++) {
        ListNode* next = cur->next;
        cur->next = next->next;
        next->next = pre->next;
        pre->next = next;
    }
    return dummy->next;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode* dummy = new ListNode(0);
    dummy->next = head;
    ListNode* pre = dummy;

    while (true) {
        // 检查剩余够不够 k 个
        ListNode* check = pre;
        for (int i = 0; i < k; i++) {
            check = check->next;
            if (!check) return dummy->next;
        }

        // 反转 k 个
        ListNode* cur = pre->next;
        for (int i = 0; i < k - 1; i++) {
            ListNode* next = cur->next;
            cur->next = next->next;
            next->next = pre->next;
            pre->next = next;
        }
        pre = cur;  // 下一组的 pre 就是这组的尾
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode* dummy = new ListNode(0);
    ListNode* cur = dummy;

    while (l1 && l2) {
        if (l1->val < l2->val) {
            cur->next = l1;
            l1 = l1->next;
        } else {
            cur->next = l2;
            l2 = l2->next;
        }
        cur = cur->next;
    }
    cur->next = l1 ? l1 : l2;  // 剩下的直接接上
    return dummy->next;
}

1
2
3
4
5
6
7
8
9

bool hasCycle(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

ListNode* detectCycle(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            slow = head;
            while (slow != fast) {
                slow = slow->next;
                fast = fast->next;
            }
            return slow;
        }
    }
    return nullptr;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

ListNode* removeElements(ListNode* head, int val) {
    ListNode* dummy = new ListNode(0);
    dummy->next = head;
    ListNode* cur = dummy;

    while (cur->next) {
        if (cur->next->val == val) {
            cur->next = cur->next->next;
        } else {
            cur = cur->next;
        }
    }
    return dummy->next;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* dummy = new ListNode(0);
    dummy->next = head;
    ListNode *fast = dummy, *slow = dummy;

    for (int i = 0; i <= n; i++) fast = fast->next;
    while (fast) {
        fast = fast->next;
        slow = slow->next;
    }
    slow->next = slow->next->next;
    return dummy->next;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
    ListNode *pA = headA, *pB = headB;
    // 指针 A 走完 A 走 B，指针 B 走完 B 走 A
    // 有交点会在交点相遇，没交点都走到 nullptr
    while (pA != pB) {
        pA = pA ? pA->next : headB;
        pB = pB ? pB->next : headA;
    }
    return pA;
}