手撕代码之链表_手撕树和链表的题怎么写输入输出

  【注意1】：对于链表的问题，根据以往的经验一般都是要建一个dummy node，连上原链表的头结点，这样的话就算头结点变动了，我们还可以通过dummy->next来获得新链表的头结点。。

  【注意2】：链表的问题很多都可以使用双指针解决，有时候是快慢指针。

// 创建链表和输出链表
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct ListNode
{
	int val;
	ListNode *next;
	ListNode(int value) : val(value), next(nullptr) { }
};

ListNode *test_fun(ListNode *l1) {

}

int main() {
	vector<int> data1 = { 2,4,3 };
	ListNode *head1 = new ListNode(data1[0]), *ptr1 = head1;
	for (int i = 1; i < data1.size(); ++i) {
		ListNode *tmp1 = new ListNode(data1[i]);
		ptr1->next = tmp1;
		ptr1 = tmp1;
	}
	ptr1->next = nullptr;
	
	ListNode *ptr_tmp = test_fun(head1);
	while (ptr_tmp) {
		cout << ptr_tmp->val << endl;
		ptr_tmp = ptr_tmp->next;
	}
	system("pause");
	return 0;
}
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

一、反转链表（leetcode 206）

  思路：用两个指针记录下当前指针的前驱和后继，然后不断更新指针的指向，保存当前结点的下一个结点，防止链表断裂找不到后继。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 用两个指针记录下当前指针的前驱和后继，然后不断更新指针的指向
        ListNode *pPre = nullptr, *pNext; 
        while (head != nullptr){
            // 保存当前结点的下一个结点，防止链表断裂找不到后继
            pNext = head->next;
            // 修改当前结点的指向
            head->next = pPre;
            // 更新指针
            pPre = head;
            head = pNext;
        }
        return pPre;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

二、两个链表的交点（leetcode 160）

  思路：先计算两个链表的长度，让长度较长的链表先走一段距离，之后两个结点齐头并进，如果相遇则找到相交的结点了。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int len1 = 0, len2 = 0;
        ListNode *tmpA = headA;
        ListNode *tmpB = headB;
        // 先计算两个链表的长度
        while (tmpA != nullptr){
            len1++;
            tmpA = tmpA->next;
        }
        while (tmpB != nullptr){
            len2++;
            tmpB = tmpB->next;
        }
        if (len1 > len2){
            int tmp = len1 - len2;
            // 让长度较长的链表先走一段距离
            for (int i = 0; i < tmp; ++i)
                headA = headA->next;
            // 之后两个结点齐头并进，如果相遇则找到相交的结点了
            while (headA != nullptr && headB != nullptr){
                if (headA == headB)
                    return headA;
                headA = headA->next;
                headB = headB->next;
            }
        }
        else{
            int tmp = len2 - len1;
            for (int i = 0; i < tmp; ++i)
                headB = headB->next;
            while (headB != nullptr && headA != nullptr){
                if (headB == headA)
                    return headB;
                headA = headA->next;
                headB = headB->next;
            }
        }
        return nullptr;
    }
};
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

三、链表的中间结点（leetcode 876）

  思路：快慢指针，快指针每次走两步，慢指针每次走一步，当快指针到头了，那么慢指针就是中间结点。

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode *pTmp = head;
        while (head != nullptr && head->next != nullptr){
            // 快慢指针，快指针每次走两步，慢指针每次走一步，当快指针到头了，
            // 那么慢指针就是中间结点
            pTmp = pTmp->next;
            head = head->next->next;
        }
        return pTmp;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

四、判断链表是否存在环（leetcode 141）

  思路：快慢指针，快指针每次走两步，慢指针每次走一步，当快慢指针相遇时，即链表存在环。

class Solution {
public:
    bool hasCycle(ListNode *head) {
        // 快慢指针
	    ListNode *pSlow = head, *pFast = head;
	    while (pSlow != nullptr && pFast != nullptr && pFast->next != nullptr)
	    {
	    	pSlow = pSlow->next;
	    	pFast = pFast->next->next;
            // 当快慢指针相遇时，即链表存在环
            if (pSlow == pFast)
	    		return true;
		}
		return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

五、输出链表环的入口结点（leetcode 142）

  思路：先使用快慢指针找到相遇的结点，将慢指针移动到头结点，然后快慢指针前进速度变为一样，之后再相遇则为入口结点。

  图中，head到环路起点的距离为K，起点到fast和slow的相遇点的距离为M，环路周长为L。假设，在fast和slow相遇时，fast走过了Lfast，slow走过了Lslow。根据题意：Lslow=K+M；Lfast=K+M+nL（n为正整数）；Lfast=2Lslow。可以推出：Lslow=nL；K=nL-M。则当slow重新回到head，而fast还在相遇点，slow和fast都向前走，且每次走一个节点。则slow从head走到起点走了K，而fast从相遇点出发也走了K，而fast向前走了距离K后到了哪里呢？由于K=（n-1）*L+（L-M），所以fast转了n-1圈，再走L-M，也到了起点。这样起点就找到了。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *pSlow = head, *pFast = head;
        // 先使用快慢指针找到相遇的结点
        while (pFast != nullptr && pFast->next != nullptr){
            pSlow = pSlow->next;
            pFast = pFast->next->next;
            if (pSlow == pFast)
                break;
        }
        if (pFast == nullptr || pFast->next == nullptr)
            return nullptr;
        // 将慢指针移动到头结点，然后快慢指针前进速度变为一样，之后再相遇则为入口结点
        pSlow = head;
        while (pSlow != pFast){
            pSlow = pSlow->next;
            pFast = pFast->next;            
        }
        return pSlow;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

六、删除链表中倒数第k个节点（leetcode 19）

  思路：使用双指针，让其中一个指针先走K步，当它到达链表尾部了，则另一个指针为倒数第K个结点。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if (head == nullptr) return nullptr;
        ListNode *p1 = head, *p2 = head;
        // 使用双指针找到倒数第K个结点
        for (int i = 0; i < n; ++i){
            p2 = p2->next;
        }
        if (p2 == nullptr)
            return head->next;
        while (p2->next != nullptr){
            p1 = p1->next;
            p2 = p2->next;
        }
        // 删除第K个结点
        p1->next = p1->next->next;
        return head;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

七、合并两个排序链表（leetcode 21）

  思路：新链表的头结点是两个链表中较小的一个，头结点的下一个结点则是由原来较小的链表的下一个结点和原来较长的链表产生，是一个递归过程。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *pHead;
        // 某一个链表为空则返回较长的那个
        if (l1 == nullptr) return l2;
        if (l2 == nullptr) return l1;
        if (l1->val <= l2->val){
            // 新链表的头结点是两个链表中较小的一个
            pHead = l1;
            // 新链表的下一个结点则是由原来较小的链表的下一个结点和原来较长的链表产生
            pHead->next = mergeTwoLists(l1->next, l2);
        }
        else{
            pHead = l2;
            pHead->next = mergeTwoLists(l1, l2->next);               
        }
        return pHead;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

八、O(1)时间删除链表中的一个结点（leetcode 237）

  思路：保存当前结点的下一个结点，把下一个结点复制给当前结点，删除下一个结点。

class Solution {
public:
    void deleteNode(ListNode* node) {
        // 保存当前结点的下一个结点
        ListNode *pTemp = node->next;
        // 把下一个结点复制给当前结点
        node->val = pTemp->val;
        node->next = pTemp->next;
        // 删除下一个结点
        delete pTemp;
        pTemp = nullptr;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

九、删除重复的结点（leetcode 83）

  思路：双指针，记录下一个结点是否和当前结点相等，如果两个结点相等，则删除后面一个结点。

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (head == nullptr || head->next == nullptr) return head;
        // 双指针，记录下一个结点是否和当前结点相等，如果两个结点相等，则删除后面一个结点
        ListNode *p1 = head, *p2 = head->next;
        while (p2 != nullptr){
            if (p1->val == p2->val){
                p1->next = p2->next;
                p2 = p2->next;
            }else{
                p1 = p1->next;
                p2 = p2->next;
            }
        }
        return head;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

十、删除链表中所有指定的节点（leetcode 203）

  思路：对于要删除节点的题目，可以先创建一个不存在的新节点。至于本题，对于当前的指针，如果下一个节点值和当前想等，则直接移动指针指向。

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if (head == nullptr) return head;
        // 创建一个不存在的新节点
        ListNode* ptr_newhead = new ListNode(-1);
        ptr_newhead->next = head;
        ListNode *cur = ptr_newhead;
        while (cur != nullptr && cur->next != nullptr) {
            // 遇到相同的元素则移动当前指针的指向
            if (cur->next->val == val){
                cur->next = cur->next->next;
            } else {
                cur = cur->next;
            }
        }
        return ptr_newhead->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

十一、链表重排/对折（leetcode 143）

  思路：分三步走：第一步，使用快慢指针找到中间节点；第二步，翻转后半段；第三步，将两段连接起来。

class Solution {
public:
    void reorderList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) return;
        // 先使用快慢指针找到中间节点
        ListNode *fast = head, *slow = head;
        while (fast->next != nullptr && fast->next->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        // 然后翻转后半部分的链表
        ListNode *cur = slow->next;
        slow->next = nullptr;
        ListNode *cur_pre = nullptr;
        while (cur != nullptr) {
            ListNode *cur_next = cur->next;
            cur->next = cur_pre;
            cur_pre = cur;
            cur = cur_next;
        }
        // 最后将两段链表插空连接起来
        ListNode *first = head, *second = cur_pre;
        while (first != nullptr && second != nullptr) {
            ListNode *first_next = first->next;
            first->next = second;
            ListNode *second_next = second->next;
            second->next = first_next;
            first = first_next;
            second = second_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

十二、链表排序（leetcode 148）

  思路：使用快排对链表排序。

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        QuickSortList(head, nullptr);
        return head;
    }
    // 分别对前半部分和后半部分排序
    void QuickSortList(ListNode* pBegin, ListNode* pEnd) {
        if (pBegin != pEnd){
            ListNode *pMid = partition(pBegin, pEnd);
            QuickSortList(pBegin, pMid);
            if (pMid->next)
                QuickSortList(pMid->next, pEnd);
        }
    }
    // 一次划分（和数组类似）
    ListNode* partition(ListNode* pBegin, ListNode* pEnd){
        ListNode *pMid = pBegin, *pTmp = pMid->next;
        while (pTmp != pEnd){
            if (pTmp->val < pBegin->val){
                pMid = pMid->next;
                swap(pMid->val, pTmp->val);
            }
            pTmp = pTmp->next;
        }
        swap(pMid->val, pBegin->val);
        return pMid;
    }
};
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

十三、调整链表顺序使奇数位置的结点位于偶数位置结点的前面（leetcode 328）

  思路：用两个奇偶指针分别指向奇偶节点的起始位置，用一个单独的指针even_head来保存偶节点的起点位置，然后把奇节点的指向偶节点的下一个(一定是奇节点)，把奇节点后移一步，再把偶节点指向下一个奇节点的下一个(一定是偶节点)，把偶节点后移一步，以此类推直至末尾，此时把分开的偶节点的链表连在奇节点的链表后即可。

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode *odd = head, *even = head->next, *even_head = even;
        while (even != nullptr && even->next != nullptr){
            odd = odd->next = even->next;
            even = even->next = odd->next;
        }
        odd->next = even_head;
        return head;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

十四、合并k个有序链表（leetcode 23）

  思路：使用优先队列存储k个链表的每一个元素，它们会自动排好序，然后重新建立一个新的链表。

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // 使用优先队列存储k个链表的每一个元素，它们会自动排好序
        priority_queue<int, vector<int>, greater<int>> pq;
        for (auto node : lists) {
            while (node) pq.push(node->val), node = node->next;
        }
        // 先创建一个首节点
        ListNode *ptr_pre = new ListNode(-1), *ptr = ptr_pre;
        while (!pq.empty()) {
            ListNode *node = new ListNode(pq.top());
            ptr->next = node;
            ptr = ptr->next;
            pq.pop();
        }
        return ptr_pre->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

十五、部分翻转链表（leetcode 92）

  思路：建一个dummy node，连上原链表的头节点，定义pre、cur节点。后续的操作是先取出当前节点的下一个节点，然后插入到要翻转的位置上，不断把后面的元素插入到前面。

class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        // 建一个dummy node，连上原链表的头结点
        ListNode *dummy = new ListNode(-1), *pre = dummy;
        dummy->next = head;
        for (int i = 0; i < m-1; ++i)
            pre = pre->next;
        ListNode *cur = pre->next;
        // 后续的操作是先取出当前节点的下一个节点，然后插入到要翻转的位置上，不断把后面的元素插入到前面
        for (int i = m; i < n; ++i) {
            ListNode *tmp = cur->next;
            cur->next = tmp->next;
            tmp->next = pre->next;
            pre->next = tmp;
        }
        return dummy->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

十六、链表相加（leetcode 2）

  思路：每次加完之后，创造一个新的结点，让当前结点指向它，并移动当前结点。

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int carry = 0, sum = 0;
        // 先创造一个前驱结点，并赋值给当前结点
        ListNode *ptr_pre = new ListNode(-1);
        ListNode *ptr = ptr_pre;
        while (l1 || l2 || carry){
            if (l1){
                sum += l1->val;
                l1 = l1->next;
            }
            if (l2){
                sum += l2->val;
                l2 = l2->next;
            }
            if (carry){
                sum += carry;
                carry = 0;
            }
            // 计算进位
            carry = sum / 10;
            sum %= 10;
            // 创造一个新的结点，让当前结点指向它，并移动当前结点
            ptr->next = new ListNode(sum);
            ptr = ptr->next;
            sum = 0;
        }
        ptr->next = nullptr;
        // 返回前驱结点的下一个结点
        ptr = ptr_pre->next;
        return ptr;
    }
};
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