FisherYu626

一颗有趣的灵魂~

0%

链表算法笔记

发表于 分类于
本文字数： 1.8k 阅读时长 ≈ 2 分钟

链表算法笔记

1.删除链表的倒数第n个节点

凡是头结点可能发生变化，先建立一个虚拟头结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ListNode* removeNthFromEnd(ListNode* head, int k) {
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;

        int n = 0;//此处长度为包含虚拟头结点长度
        for(auto p=dummy;p;p=p->next) n++;
        
        
        auto p=dummy;
        for(int i = 0;;i<n-k-1;i++) p =p ->next;
        
        p->next = p->next->next;

        return dummy->next;
    }

2.回文链表

image-20220403221154593

先定位至链表后一半位置，再讲后一半进行倒序。

双指针同时从后往前进行比较。

比较完毕后将原链表恢复，负责lc报错。

！！！反转已反转的后半部分链表需要将最后一个节点的写一个指针置为空。

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
bool isPalindrome(ListNode* head) {

        auto a = head;
        auto start = head;
        int n = 0;
        while(a){
            n++;
            a = a->next;
        }
        if(n <= 1) return true;

        a = head;
        for(int i = 0;i<n-n/2;i++){
            a = a->next;
        }
        auto b = a->next;

        for(int i = 0;i<n/2-1;i++){
            auto c = b->next;
            b->next = a;
            a = b;
            b = c;
        }
        
        auto tail = a;
        
        bool success = true;
        for(int i = 0;i<n/2;i++){
            if(a->val != start->val){
                success = false;
                break;
            }
            a = a->next;
            start = start->next;
        }
        
        a = tail;
        b = a->next;
        for(int i = 0;i<n/2-1;i++){
            auto c = b->next;
            b->next = a;
            a = b;
            b = c;
        }
        tail->next = NULL;

        return success;
    }

3.环形链表

检查一个链表是否存在环

解决方案：快慢指针 快指针每次前进2步，慢指针一次前进1步。如果存在环，则快指针早晚会相遇。

1
2
3
4
5
6
7
8
9
10
11
12
13
bool hasCycle(ListNode *head) {
        if(!head||!head->next) return false;
        auto s = head,f = head->next;
        while (f)
        {
            s = s->next;
            f = f->next;
            if(!f) return false;
            f = f->next;
            if(s == f) return true;
        }
        return false;
    }

进阶：

返回环的起点位置

image-20220404122250260

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
ListNode *detectCycle(ListNode *head) {
        if(!head||!head->next) return NULL;
        auto s = head,f = head->next;
        while(f){
            s = s->next;
            f = f->next;
            if(!f) return NULL;
            f = f->next;
            if(s == f){
                s = head;
                //s指向head相当于从虚头前进一步
                //为保持同步，让f前进一步！！
                f = f->next;
                while(s!=f){
                    s = s->next;
                    f = f->next;
                }
                return s;
            }
        }
        return NULL;
    }

image-20220404123643814