链表总结

基础操作

用数组获得链表，用尾插法，迭代正向输出，递归反向输出

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

void dispListNode(ListNode *head) {
    while (head) {
        cout << head->val << " ";
        head = head->next;
    }
}

void revDispListNode(ListNode *head) {
    if (!head) return;
    revDispListNode(head->next);
    cout << head->val << " ";
}

// 数组构建链表，尾插法
ListNode* getListNode(const vector<int>& nums) {
    ListNode *head = new ListNode(-1);
    ListNode *dummy = head;
    for (auto& n : nums) {
        ListNode *node = new ListNode(n);
        head->next = node;
        head = head->next;
    }
    return dummy->next;
}

int main(int argc, char const *argv[])
{
    vector<int> nums = {1, 2, 3, 4};
    ListNode *head = getListNode(nums);
    dispListNode(head);
    cout << endl;
    revDispListNode(head);  // 反向输出
    cout << endl;
    return 0;
}
1 2 3 4
4 3 2 1

---

设计链表

class MyLinkedList {
public:
    ListNode *_dummy = new ListNode(0);
    int _size = 0;
    MyLinkedList() {}
    
    int get(int index) {    // 等于也不行，因为是空
        if (index >= _size || index < 0) return -1;
        ListNode *cur = _dummy;
        while (index--) {
            cur = cur->next;    // index-1
        }
        return cur->next->val;  // 返回next的值
    }
    
    void addAtHead(int val) {
        ListNode *node = new ListNode(val);
        node->next = _dummy->next;
        _dummy->next = node;
        _size++;
    }
    
    void addAtTail(int val) {
        ListNode *cur = _dummy;
        while (cur->next) cur = cur->next;  // 找到最后一个元素
        ListNode *node = new ListNode(val);
        cur->next = node;
        _size++;
    }
    
    void addAtIndex(int index, int val) {
        if (index > _size) return;  // 等于可以，因为要新建元素
        ListNode *cur = _dummy;
        while (index--) cur = cur->next;    // index-1
        ListNode *node = new ListNode(val);
        node->next = cur->next;          // 插入到next位置
        cur->next = node;
        _size++;
    }
    
    void deleteAtIndex(int index) { // 等于也不行，因为是空
        if (index >= _size || index < 0) return; 
        ListNode *cur = _dummy;
        while (index--) cur = cur->next;    // index-1
        cur->next = cur->next->next;        // 删除next
        _size--;
    }
};

---

反转

全局反转

206-反转链表

递归

ListNode* reverseList(ListNode* head) {
    if (!head || !head->next) return head;  // 空节点或最后一个节点
    ListNode *node = reverseList(head->next);
    head->next->next = head;    // 下一个节点指向自己
    head->next = nullptr;       // 自己指针置空
    return node;    // 反转后的头结点
}

迭代

ListNode* reverseList(ListNode* head) {
    if (!head) return head;
    ListNode *pre = nullptr;
    while (head) {
        ListNode *tmp = head->next;
        head->next = pre;
        pre = head;
        head = tmp;
    }
    return pre;
}

局部反转

92-反转链表II

反转[left, right]

// 局部反转 [head, tail)
ListNode* reverse(ListNode *head, ListNode* tail) {
    ListNode *pre = tail;
    while (head != tail) {
        ListNode *tmp = head->next;
        head->next = pre;
        pre = head;
        head = tmp;
    }
    return pre;
}
ListNode* reverseBetween(ListNode* head, int left, int right) {
    ListNode *dummy = new ListNode(0, head);
    int len = right - left + 1;     // 先记录长度
    ListNode *start = dummy;
    while (--left) start = start->next; // left的前一个，因为要做连接
    ListNode *end = start->next;
    while (len--) end = end->next;  // 指向right的后一个
    start->next = reverse(start->next, end);    // 注意连接
    return dummy->next;
}

---

环形链表

判断是否有环

141-环形链表

双指针

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

判断环的位置

142-环形链表II

相遇之后一个从相遇节点开始走，一个从头结点开始走，再次相遇的位置就是环入口

ListNode *detectCycle(ListNode *head) {
    ListNode *fast = head;
    ListNode *slow = head;
    while (fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
        if (slow == fast) { // 一个相遇节点开始走
            slow = head;    // 另一个从头开始走
            while (slow != fast) {
                slow = slow->next;
                fast = fast->next;
            }
            return fast;
        }
    }
    return nullptr;
}

---

相交链表

A:          a1 → a2
                    ↘
                      c1 → c2 → c3
                    ↗
B:    b1 → b2 → b3

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode *pA = headA;
    ListNode *pB = headB;
    while (pA != pB) {
        if (pA) pA = pA->next;
        else pA = headB;
        if (pB) pB = pB->next;
        else pB = headA;
    }
    return pA;
}

删除重复元素

递归

ListNode* deleteDuplicates(ListNode* head) {
    if (!head) return head;
    head->next = deleteDuplicates(head->next);
    if (head->next && head->val == head->next->val) {
        return head->next;  // 直接返回下一个节点，当前节点就没了
    }
    return head;
}

迭代

ListNode* deleteDuplicates(ListNode* head) {
    ListNode *cur = head;
    while (cur) {
        while (cur->next && cur->next->val == cur->val) {
            cur->next = cur->next->next;
        }
        cur = cur->next;
    }
    return head;
}