链表常见面试题_哨兵解决边界问题

链表注意点

1、警惕指针丢失和内存泄漏（单链表）
（1）插入节点
在节点a和节点b之间插入节点x，b是a的下一节点，p指针指向节点a。

造成指针丢失和内存泄漏的代码：
p—>next = x; x—>next = p—>next; 这会导致x节点的后继指针指向自身。

正确的写法是2句代码交换顺序，即：
x—>next = p—>next; p—>next = x;
（2）删除节点
在节点a和节点b之间删除节点b，b是a的下一节点，p指针指向节点a：
p—>next = p—>next—>next;

2、重点留意边界条件处理
经常用来检查链表是否正确的边界4个边界条件：
（1）如果链表为空时，代码是否能正常工作？
（2）如果链表只包含一个节点时，代码是否能正常工作？
（3）如果链表只包含两个节点时，代码是否能正常工作？
（4）代码逻辑在处理头尾节点时是否能正常工作？

3、利用“哨兵”简化实现难度

链表中的“哨兵”节点是解决边界问题的，不参与业务逻辑。
如果我们引入“哨兵”节点，则不管链表是否为空，head指针都会指向这个“哨兵”节点。
有“哨兵”节点的链表称为带头链表
没有“哨兵”节点的链表就称为不带头链表。

针对链表的插入、删除操作，需要对插入第一个节点和删除最后一个节点的情况进行特殊处理。这样代码就会显得很繁琐，所以引入“哨兵”节点来解决这个问题。

例如：
未引入“哨兵”的情况
如果在p节点后插入一个节点，只需2行代码即可搞定：
new_node—>next = p—>next;
p—>next = new_node;

但是如果向空链表中插入一个节点，则代码如下：
if(head == null){
head = new_node;
}
如果要删除节点p的后继节点，只需1行代码即可搞定：
p—>next = p—>next—>next;

但是如果删除链表的最有一个节点（链表中只剩下这个节点），则代码如下：
if(head—>next == null){
head = null;
}

“哨兵”节点不存储数据，无论链表是否为空，head指针都会指向它，作为链表的头结点始终存在

哨兵最大的作用就是简化边界条件的处理。有了哨兵，插入第一个节点和插入其他节点，删除最后一个节点和删除其他节点都可以统一为相同的代码实现逻辑了。

leetcode相关题目

单链表反转

https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/

方法一：非迭代方式实现

/**
 * 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) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while(curr != nullptr) {
            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
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* reverseList(ListNode* head) {
        if(head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode* new_head = reverseList(head->next);
        ListNode* tmp = new_head;
        while(tmp->next != nullptr) {
            tmp = tmp->next;
        }
        tmp->next = head;
        head->next = nullptr;
        return new_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

链表中环的检测

https://leetcode-cn.com/problems/linked-list-cycle/
方法一：检测是否有相同的指针

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == NULL || head->next == NULL) return false;
        unordered_set<ListNode *> node_set;
        node_set.clear();
        ListNode * p = head;
        bool has_cycle = false;
        while(p != nullptr) {
            if (node_set.count(p)) {
                has_cycle = true;
                break;
            }
            node_set.insert(p);
            p = p->next;
        }
        return has_cycle; 
    }
};
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

方法二：快慢指针

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == NULL || head->next == NULL) return false;
        ListNode * slow = head;
        ListNode * fast = head->next;
        while (slow != fast) {
            if (fast == NULL || fast->next == NULL) {
                return false;
            }
            slow = slow->next;
            fast = fast->next->next;
        }
        return true;  
    }
};
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

求链表相交的起点

https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/
输入两个链表，找出它们的第一个公共节点。

方法一：使用set将一个链表中的节点保存下来

/**
 * 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) {
        unordered_set<ListNode *> nodeset;
        ListNode * a = headA;
        while(a != nullptr) {
            nodeset.insert(a);
            a = a->next;
        }
        ListNode * b = headB;
        ListNode * result = nullptr;
        while(b != nullptr) {
            if(nodeset.find(b) != nodeset.end()) {
                result = b;
                break;
            }
            b = b->next;
        }
        return result;
    }
};
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

方法二：先计算两个链表的长度，如果某一链表长n步，则先走n步，然后两个再同时走，判断是否相同。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int getLength(ListNode * head) {
        int length = 0;
        while(head != nullptr) {
            head = head->next;
            length++;
        }
        return length;
    }
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int lengtha = getLength(headA);
        int lengthb = getLength(headB);
        ListNode *a = headA;
        ListNode *b = headB;
        while(lengtha - lengthb > 0) {
            a = a->next;
            lengtha--;
        }
        while(lengthb - lengtha > 0) {
            b = b->next;
            lengthb--;
        }
        ListNode * res = nullptr;
        while(a != nullptr && b != nullptr) {
            if(a == b) {
                res = a;
                break;
            }
            a = a->next;
            b = b->next;
        }
        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
33
34
35
36
37
38
39
40
41
42
43

两个有序链表合并

https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 == nullptr || l2 == nullptr) {
            if (l1 == nullptr) {
                return l2;
            }
            if (l2 == nullptr) {
                return l1;
            }
        }
        ListNode* head = new ListNode(0);
        ListNode* node = head;
        if(l1->val < l2->val) {
            head->val = l1->val;
            l1 = l1->next;
        } else {
            head->val = l2->val;
            l2 = l2->next;
        }
        while(l1 != nullptr && l2 != nullptr) {
            if (l1->val < l2->val) {
                node->next = l1;
                l1 = l1->next;
            } else {
                node->next = l2;
                l2 = l2->next;
            }
            node = node->next;
        }
        if (l1 != nullptr) {
            node->next = l1;
        } else if (l2 != nullptr) {
            node->next = l2;
        } 
        return 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
35
36
37
38
39
40
41
42
43
44
45
46
47