链表专题

发表于 | 更新于 | 评论数： | 阅读次数： | 阅读次数：

19. Remove Nth Node From End of List

  • 建立虚拟头节点（因为可能删除头节点）， first, second 指向dummy（虚拟头节点）
  • first指针向后走n步， 然后 first, second同时向后走， 直到 first到达最后一个元素
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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int cnt = 0;
        auto dummy = new ListNode(0);
        dummy->next = head;
        auto first = dummy, second = dummy;
        while(n--) {
            first = first->next;
        }
        while(first->next) {
            first = first->next;
            second = second->next;
           
        }
        
        second->next = second->next->next;
        
        return dummy->next;
    }
};

237. Delete Node in a Linked List

##

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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val = node->next->val;
        node->next = node->next->next;
    }
};

##
也可以缩成一句话 *(node) = *(node->next); 结构体的等号就是直接复制

[83. Remove Duplicates from Sorted List] (https://leetcode.com/problems/remove-duplicates-from-sorted-list/)

1
2


61. Rotate List

与19题一样，使用了双指针

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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(!head) return nullptr;
        auto first = head, second = head;
        int cnt = 0;
        
        for (auto p = head; p; p = p->next) cnt++; //这一步 遍历链表， 获得链表元素个数
        
        k %= cnt;
        while(k--) first = first->next;    
        while(first->next) {
            first = first->next;
            second = second->next;
        }
        //注意这下面的几步操作
        first->next = head;
        head = second->next;
        second->next = NULL;
      
            
        return head;
        
    }
};

[24. Swap Nodes in Pairs] (https://leetcode.com/problems/swap-nodes-in-pairs/)

由于头节点会变， 所以要设置一个虚拟头节点

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        auto dummy = new ListNode(-1);
        dummy->next = head;
        
        for (auto p = dummy; p->next && p->next->next;) {   //这里用的for循环
            auto a = p->next, b = p->next->next;
            
            p->next = b; //不可或缺，因为头节点的位置改变了
            a->next = b->next;
            b->next = a;
            p = a;
          
        }
         
        return  dummy->next;
      
    }
};


按顺序做完以上三步后， 更新 p 指针 指向 a的位置

[206. Reverse Linked List] (https://leetcode.com/problems/reverse-linked-list/)

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head) return head;
        
        auto a = head, b = head->next;
        
        while (b) {
            auto c = b->next;  //c 是 b的下一个节点
            b->next = a;
            a = b;
            b = c;            
        }
        
        head->next = nullptr;
       
        return a;
        
    }
};

92. Reverse Linked List II

反转 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
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if (m == n) return head;
        
        auto dummy = new ListNode(-1);
        dummy->next = head;            //设置虚拟节点不要忘了这一步（将虚拟节点与实际链表联系起来）
        
        auto a = dummy, d = dummy;
        for (int i = 0; i < m - 1; i++) a = a->next;
        for (int i = 0; i < n; i++) d = d->next;
        
        auto b = a->next, c = d->next;
        
        for (auto p = b, q = b->next; q != c;) {
            auto o = q->next;
            q->next = p;
            p = q, q = o;
        }
        
        b->next = c;
        a->next = d;
        
        return dummy->next;
        
    }
};

160. Intersection of Two Linked Lists

神奇的做法:

如果 a != b 那么二者在交点相遇； 反之 二者走完 a+b+c 步后在交点相遇

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        auto p = headA, q = headB;
        while (p != q) {
            if (p) p = p->next;
            else p = headB;
            if (q) q = q->next;
            else q = headA;
        }
        
        return p;
    }
};

142. Linked List Cycle II

fast指针每次走两步， slow指针每次走一步
当二者相遇，说明存在环； 把slow放回head, 然后两个指针每次都走一步， 相遇点即为环的入口。

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        auto slow = head, fast = head;
        while (fast) {
            fast = fast->next;
            slow = slow->next;
            if(fast) fast = fast->next;
            else break;
            
            if (slow == fast) {
                slow = head;
                while (slow != fast) {
                    fast = fast->next;
                    slow = slow->next;
                }
                
                return slow;
            }
        }
        
        
    return nullptr;
     
    }
};

148. Sort List

1
2


0%