链表理论基础

移除链表元素

力扣——移除链表元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ListNode* removeElements(ListNode* head, int val) {
    ListNode* vHead = new ListNode();
    vHead->next = head;
    ListNode* pre = vHead;
    ListNode* p=pre->next;
    while(p!=nullptr){
        if(p->val == val){
            ListNode* temp = pre->next;
            pre->next = temp->next;
            p = pre->next;
            delete temp;
        }
        else{
            p = p->next;
            pre=pre->next;
        }
    }
    head = vHead->next;
    delete vHead;
    return head;
}

时间复杂度：O(n)
空间复杂度：O(1)

设计链表

反转链表

力扣——反转链表

我曾经用的办法是遍历已有链表，头插法创建一个新链表。缺点：创建一个新的链表
时间复杂度：O(n)
空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
ListNode* reverseList(ListNode* head) {
    ListNode* newHead = new ListNode();
    newHead->next = nullptr;
    ListNode* p = head;
    
    while(p!=nullptr){
        ListNode* newNode = new ListNode(p->val,newHead->next);
        newHead->next = newNode;
        p=p->next;
    }    ListNode* res = newHead->next;
    delete newHead;
    return res;
}

时间复杂度：O(n)
空间复杂度：O(n)

其他方法有：

  • 双指针法（原地操作）
1
2
3
4
5
6
7
8
9
10
11
ListNode* reverseList(ListNode* head) {
    ListNode* p = head;
    ListNode* pre = nullptr;
    while(p!=nullptr){
        ListNode* temp = p->next;
        p->next = pre;
        pre = p;
        p = temp;
    }
    return pre;
}

时间复杂度：O(n)
空间复杂度：O(1)

  • 递归法（将双指针法的循环体替换为递归）
1
2
3
4
5
6
7
8
9
10
11
12
ListNode* reverseList(ListNode* head) {
    return reverse(nullptr,head);
}

ListNode* reverse(ListNode* pre,ListNode* p){
    if(p==nullptr) return pre;
    ListNode* temp = p->next;
    p->next = pre;
    //pre = p;
    //p = temp;
    return reverse(p,temp); //等价于上面两步
}

时间复杂度：O(n)
空间复杂度：O(n)

两两交换链表中的节点

力扣——两两交换链表中的节点

我的方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
ListNode* swapPairs(ListNode* head) {
    if(head == nullptr) return head;
    ListNode* pHead = new ListNode();
    pHead->next = head;
    ListNode* tempPre = pHead;
    ListNode* pre = head;
    ListNode* p = head->next;
    while(pre!=nullptr && p!=nullptr){
        tempPre->next = p;
        pre->next = p->next;
        p->next = pre;
        tempPre = pre;
        pre = tempPre->next;
        p = pre == nullptr? nullptr : pre->next;
    }
    ListNode* res = pHead->next;
    delete pHead;
    return res;
}

时间复杂度：O(n)
空间复杂度：O(n)

下面是官方给出的更为清晰的答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ListNode* swapPairs(ListNode* head) {
    ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
    dummyHead->next = head; // 将虚拟头结点指向head，这样方便后面做删除操作
    ListNode* cur = dummyHead;
    while(cur->next != nullptr && cur->next->next != nullptr) {
        ListNode* tmp = cur->next; // 记录临时节点
        ListNode* tmp1 = cur->next->next->next; // 记录临时节点
        cur->next = cur->next->next;    // 步骤一
        cur->next->next = tmp;          // 步骤二
        cur->next->next->next = tmp1;   // 步骤三
        cur = cur->next->next; // cur移动两位，准备下一轮交换
    }
    ListNode* result = dummyHead->next;
    delete dummyHead;
    return result;
}

注和官方相同，但我的方法不是那么清晰，有打补丁的嫌疑（

删除链表的倒数第N个节点

力扣——删除链表的倒数第N个节点

使用双指针。

我的方法：先将fast指针移到末尾，再将slow移到倒数第n+1位置，然后删除。

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
27
28
29
30
ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* dummyH = new ListNode();
    dummyH->next = head;
    ListNode* fast = head;
    ListNode* slow = dummyH;
    int fLength = 1;
    int sLength = 0;
    while(slow){
        if(fast->next == nullptr){
            if(fLength-sLength == n){
                //删除
                ListNode* temp = slow->next;
                slow->next = slow->next == nullptr ? nullptr : slow->next->next;
                delete temp;
                break;
            }
            else{
                slow = slow->next;
                sLength ++;
            }
        }
        else{
            fast = fast->next;
            fLength ++;
        }
    }
    ListNode* res = dummyH->next;
    delete dummyH;
    return res;
}

时间复杂度：O(n)
空间复杂度：O(1)

官方的方法：将fast移到与slow相差n+1的位置，然后fast、slow同时移动直到fast到末尾，最后删除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* dummyH = new ListNode();
    dummyH->next = head;
    ListNode* fast = dummyH;
    ListNode* slow = dummyH;
    while(n-- && fast){
        fast = fast->next;
    }
    fast = fast->next;
    while(fast){
        fast = fast->next;
        slow = slow->next;
    }
    ListNode* temp = slow->next;
    slow->next = slow->next==nullptr ? nullptr:temp->next;
    delete temp;
    ListNode* res = dummyH->next;
    delete dummyH;
    return res;
}

链表相交

力扣——链表相交

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
27
28
29
30
31
32
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode* curA = headA;
    ListNode* curB = headB;
    int aL =0;
    int bL = 0;
    while(curA){
        curA = curA->next;
        aL ++;
    }
    while(curB){
        curB = curB->next;
        bL ++;
    }
    curA = headA;
    curB = headB;
    if(bL>aL){
        swap(aL,bL);
        swap(curA,curB);
    }
    int gap = aL-bL;
    while(gap--){
        curA = curA->next;
    }
    while(curA && curB){
        if(curA == curB){
            return curA;
        }
        curA = curA->next;
        curB = curB->next;
    }
    return nullptr;
}

时间复杂度：O(n+m)
空间复杂度：O(1)

环形链表II

力扣——环形链表II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ListNode *detectCycle(ListNode *head) {
    ListNode* fast = head;
    ListNode* slow = head;
    while(fast && fast->next){
        slow = slow->next;
        fast = fast->next->next;
        if(fast == slow){
            ListNode* index1 = head;
            ListNode* index2 = fast;
            while(index1 != index2){
                index1 = index1->next;
                index2 = index2->next;
            }
            return index2;
        }
    }
    return nullptr;
}

时间复杂度：O(n)
空间复杂度：O(1)

总结