圈圈小站

quanquan's blog

0%

leetcode刷题笔记——链表

发表于 分类于

刷leetcode的链表题，记录了几道经典的题。

1、反转链表 (2)

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例：

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

法一

记录下当前结点的上一个结点和下一个结点，当前节点的next指向上一个结点，再将当前节点设为下一个结点。

next不能在一开始赋值 要考虑空链表的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};
法二：递归（针对部分已经反转的链表）

如$n_1$→…→$n_{k-1}$→$n_k$→$n_{k+1}$←…$n_m$
假设正处于$n_k$ 希望$n_{k+1}$指向$n_k$
∴$n_k$->$next$->$next$ = $n_k$

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }
        ListNode* newHead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newHead;
    }
};

空间复杂度：$O(n)O(n)$ ，其中 $n$ 是链表的长度。空间复杂度主要取决于递归调用的栈空间，最多为 $n$ 层。

2、找两个链表的交点 （160）

法一 暴力法

对链表A中的每一个结点$ a_i$，遍历整个链表 B 并检查链表 B 中是否存在结点和 $a_i$相同。

复杂度分析

  • 时间复杂度 : $O(mn)$。
  • 空间复杂度 : $O(1)$。
法二 哈希表法

遍历链表 A 并将每个结点的地址/引用存储在哈希表中。然后检查链表 B 中的每一个结点 $b_i$是否在哈希表中。若在，则 $b_i$为相交结点。

复杂度分析

  • 时间复杂度 : $O(m+n)$。
  • 空间复杂度 : $O(m)$或$O(n)$。
法三 双指针法（妙）

  • 创建两个指针PA和PB，分别位于链表A和B的头结点，然后向后逐渐遍历。

  • PA到达链表尾部时，将他重定位到链表B的头结点（注意是链表B！！！）同样地，PB到达链表尾部时，将他重定位到链表A的头结点。

  • 若某一时刻PA和PB相遇，则PA/PB为相交结点。

  • 若两个链表存在相交，则它们的末尾节点必然相同。

复杂度分析

  • 时间复杂度 : $O(m+n)$。
    • 空间复杂度 : $O(m)$或$O(n)$。
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* PA = headA;
        ListNode* PB = headB;
        while (PA!=PB){
            PA = (PA?PA->next:headB);
            PB = (PB?PB->next:headA);
        }
        return PA;
    }
};

！！！注意指针为空的情况！！！

每次遍历多走一个NULL，是因为如果没有交点，最后返回的也是NULL！！！

3、合并两个有序链表 （21）

法一 迭代

不赘述 依次比较 向后链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
       ListNode* L3=new ListNode(-1);  //设个头结点
       ListNode* p = L3;
       while (l1&&l2){
           if (l1->val<=l2->val){
               p->next = l1;
               l1 = l1->next;
           }
           else{
               p->next = l2;
               l2 = l2->next;
           }
           p = p->next;
       }
       if (l1!=nullptr)
           p->next = l1;
       else if (l2!=nullptr)
           p->next = l2;
       return L3->next;
   }

复杂度分析

  • 时间复杂度 : $O(m+n)$。

  • 空间复杂度 : $O(1)$。

法二 递归

1
2
3
4
5
6
7
8
9
10
11
12
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (!l1) return l2;
        if (!l2) return l1;
        if (l1->val<=l2->val){
            l1->next = mergeTwoLists(l1->next,l2);
            return l1;
        }
        else{
            l2->next = mergeTwoLists(l2->next,l1);
            return l2;
        }
    }

复杂度分析

  • 时间复杂度 : $O(m+n)$。

  • 空间复杂度 : $O(m+n)$。 //消耗栈空间

4、删除倒数第N个结点

在对链表进行操作时，一种常用的技巧是添加一个哑节点（dummy node），它的 $next$ 指针指向链表的头节点。这样一来，我们就不需要对头节点进行特殊的判断了。

  • 一次遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0,head);
        ListNode* second = dummy;
        ListNode* first = second->next;
        while (n&&first){
            first = first->next;
            n--;
        }
        if (!first&&n) return head;     //没有要删的
        while (first){
            second = second->next;
            first = first->next;
        }
        second->next = second->next->next;  
        ListNode* ans = dummy->next;    //重要！！！不能直接返回head
        delete dummy;
        return ans;
    }

5、*两数相加 （445）

数字最高位位于链表开始位置，示例：

1
2
输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 8 -> 0 -> 7

不改变原链表：采用栈，最后倒着连链表。

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* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* p = NULL;
        ListNode* temp = NULL;
        stack<int>a,b;
        while (l1){
            a.push(l1->val);
            l1 = l1->next;
        }
        while (l2){
            b.push(l2->val);
            l2 = l2->next;
        }
        int sum,ci=0;
        while (!a.empty()||!b.empty()){
            int num1 = (a.empty()?0:a.top());
            int num2 = (b.empty()?0:b.top());
            sum = (num1+num2+ci)%10;
            ci = (num1+num2+ci)/10;
            temp = new ListNode(sum);
            temp->next = p;
            p = temp;
            if (!a.empty()) a.pop();
            if (!b.empty()) b.pop();
        }
        if (ci){
            temp = new ListNode(ci);
            temp->next = p;
        }
        return temp;
    }

复杂度分析

  • 时间复杂度 : $O(max(m,n))$。

  • 空间复杂度 : $O(m+n)$。 //消耗栈空间

不知道为啥用数组时间超了

先放着叭~

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
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* p = NULL;
        ListNode* temp = NULL;
        int a[100],b[100];
        int cnt1=0,cnt2=0;
        while (l1){
            a[cnt1++] = l1->val;
            l1 = l1->next;
        }
        while (l2){
            b[cnt2++] = l2->val;
            l2 = l2->next;
        }
        cnt1--,cnt2--;
        int sum,ci=0;
        while (cnt1||cnt2){
            int num1 = (cnt1>=0?a[cnt1]:0);
            int num2 = (cnt2>=0?b[cnt2]:0);
            sum = (num1+num2+ci)%10;
            ci = (num1+num2+ci)/10;
            temp = new ListNode(sum);
            temp->next = p;
            p = temp;
            cnt1--,cnt2--;
        }
        if (ci){
            temp = new ListNode(ci);
            temp->next = p;
        }
        return temp;
    }
};

6.*回文链表

法一 拷贝到数组里 双指针比较

复杂度分析

  • 时间复杂度 : $O(n)$。
  • 空间复杂度 : $O(n)$。

法二 链表后半部分反转

  1. 找到前半部分链表的尾节点。
  2. 反转后半部分链表。
  3. 判断是否回文。
  4. 恢复链表。

【步骤一】计算链表节点的数量，再找到前半部分的尾节点；也可以使用快慢指针在一次遍历中找到：慢指针一次走一步，快指针一次走两步，快慢指针同时出发。当快指针移动到链表的末尾时，慢指针恰好到链表的中间。

【步骤四】与步骤二函数相同，再反转一次。

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
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (head == nullptr) {
            return true;
        }
        // 找到前半部分链表的尾节点并反转后半部分链表
        ListNode* firstHalfEnd = endOfFirstHalf(head);
        ListNode* secondHalfStart = reverseList(firstHalfEnd->next);
        // 判断是否回文
        ListNode* p1 = head;
        ListNode* p2 = secondHalfStart;
        bool result = true;
        while (result && p2 != nullptr) {
            if (p1->val != p2->val) {
                result = false;
            }
            p1 = p1->next;
            p2 = p2->next;
        }        
        // 还原链表并返回结果
        firstHalfEnd->next = reverseList(secondHalfStart);
        return result;
    }

    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr != nullptr) {
            ListNode* nextTemp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
    
    ListNode* endOfFirstHalf(ListNode* head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while (fast->next != nullptr && fast->next->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }
};

7.奇偶链表

把节点编号为奇数的放在前面，偶数放在后面。

示例：

1
2
输入: 2->1->3->5->6->4->7->NULL 
输出: 2->3->6->7->1->5->4->NULL

一边扫描，时间复杂度O(n)，空间复杂度O(1).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (head==nullptr) return head;
        ListNode* odd_p = head;
        ListNode* even_head = head->next;
        ListNode* even_p = even_head;
        while (even_p&&even_p->next){
            odd_p->next = even_p->next;
            odd_p = odd_p->next;
            even_p->next = odd_p->next;
            even_p = even_p->next;
        }
        odd_p->next = even_head;
        return head;
    }
};