C++ 全栈知识体系

链表题型

前提：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
1
2
3
4
5
6
7
8
9
10

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

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

题解：

方法一:
首先遍历一遍计算出list长度len，然后找到len-n的前一个节点，改变其指向，需要注意head节点特殊处理

ListNode *removeNthFromEnd(ListNode *head, int n)
{
    int len = length(head);
    int step = len - n;

    if (step == 0)
    {
        return head->next;
    }

    ListNode *tmp1 = head;
    for (int i = 1; i < step; i++)
    {
        tmp1 = tmp1->next;
    }
    tmp1->next = tmp1->next->next;

    return head;
}

int length(ListNode *node)
{
    int size = 0;

    while (node)
    {
        size++;
        node = node->next;
    }

    return size;
}

方法二:
快慢指针，且增加一个头节点的方法

ListNode *removeNthFromEnd(ListNode *head, int n)
{
    ListNode *res = new ListNode(0, head);
    ListNode *fast = res;
    ListNode *slow = res;

    for (int i = 1; i <= n; i++)
    {
        fast = fast->next; //走n步
    }

    while (fast->next)
    {
        fast = fast->next; //走到结尾
        slow = slow->next; //走了len-n步
    }
    slow->next = slow->next->next;
    return res->next;
}
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
49
50
51
52
53
54
55
56
57
58

技巧: 快慢指针，增加一个头节点。

反转链表

反转链表

ListNode *reverseList(ListNode *head)
{
    ListNode *end = nullptr;

    if (head == nullptr || head->next == nullptr)
    {
        return head;
    }

    while (head->next)
    {
        ListNode *tmp = head->next;
        head->next = end;
        end = head;
        head = tmp;
    }

    head->next = end;

    return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

更好的解法:

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

技巧：可以尝试去判断头节点是否为空

  1. 相交链表
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        set<ListNode*> mset;

        if(headA==NULL || headB==NULL){
            return NULL;
        }

        while(headA){
            mset.insert(headA);
            headA=headA->next;
        }

        while(headB){
            if(mset.count(headB))
                return headB;
            headB=headB->next;
        }

        return NULL;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

← 各类题型 →