【刷题笔记】牛客网面试必刷101刷题笔记(1)_牛客网笔刷101

本文主要介绍的是近期刷的一些题的思路和解题过程及代码，今天为大家带来的是面试101的链表题目，也是BM1 - BM16 的所有题目，希望大家看的开心，复习愉快！

BM1 反转链表

描述

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围： 0≤n≤1000

要求：空间复杂度 O(1) ，时间复杂度 O(n)。

如当输入链表{1,2,3}时，

经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。

题解：

我们知道头节点，如果想要进行反转，就是进行

head->next->next = head;
1

这样就会造成 head之后的节点原本指向的节点失踪，也就是我们找不到原来的节点了，我们通过遍历可以解决这个问题。

思路1.

因为我们如果把当前节点的指向断掉，就无法寻找到后一个节点，所以我们用临时变量存储它，然后进行遍历即可。注意的是，我们判断结束的条件是：cur -> next 为空，最后当cur -> next为空时，需要特殊处理，令 cur->next = prev; 这样才修正了最后一个节点 cur 的指向。

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
		if(pHead == nullptr)	return nullptr;
		struct ListNode* next = nullptr;
		struct ListNode* cur = pHead;
		struct ListNode* prev = nullptr;
		while(cur->next){
			next = cur->next;
			cur->next = prev;
			prev = cur;
			cur = next;
		}
		cur->next = prev;
		return cur;
    }
};
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

思路2：

我们可以考虑用递归来处理，因为递归会让我们快速找到最后一个节点，通过自己调用自己的方式，找到自己的最后一个节点，然后让这个节点的下一个节点指向前一个节点，最终修改节点，但是时间和空间复杂度都是O(N)，因为递归调用的栈空间为N 层。

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
		if(!pHead || !pHead->next) return pHead;
		ListNode* ans = ReverseList(pHead->next);
		pHead->next->next = pHead;
		pHead->next = nullptr;
		return ans;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

BM2 链表内指定区间反转

描述

将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转
例如：
给出的链表为 1→2→3→4→5→NULL, m=2,n=4
返回 1→4→3→2→5→NULL

数据范围： 链表长度 0<size≤1000，0<m≤n≤size，链表中每个节点的值满足 ∣val∣≤1000

要求：时间复杂度 O(n) ，空间复杂度 O(n)

进阶：时间复杂度 O(n)，空间复杂度 O(1）

题解：

考虑特殊情况，如果n == m，则不用反转直接返回头节点；

如果头节点为空，直接返回空；

如果头节点的下一个节点为空，证明只有一个节点，不用反转，直接返回头节点；

肯定是要先找到了第m个位置才能开始反转链表，而反转的部分就是从第m个位置到第n 个位置，反转这部分的时候就参照 BM1.反转链表进行反转。

那么如果是指定区间的反转，我们分区间进行处理，只需要分成：

[1 , m-1] [m , n] [n+1, end]

• step 1：我们可以在链表前加一个表头，后续返回时去掉就好了，因为如果要从链表头的位置开始反转，在多了一个表头的情况下就能保证第一个节点永远不会反转，不会到后面去。
• step 2：使用两个指针，一个指向当前节点，一个指向前序节点。
• step 3：依次遍历链表，到第m个的位置。
• step 4：对于从m到n这些个位置的节点，依次断掉指向后续的指针，反转指针方向。
• step 5：返回时去掉我们添加的表头。

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        //制造头节点
        ListNode* res = new ListNode(-1);
        res->next = head;
        //前序节点
        ListNode* prev = res;
        //当前节点
        ListNode* cur = head;
        //find m
        for(int i = 1; i < m; ++i){
            prev = cur;
            cur = cur->next;
        }
        //从m 反转到n
        for(int i = m; i < n; ++i){
            ListNode* tmp = cur->next;
            cur->next = tmp->next;
            tmp->next = prev->next;
            prev->next = tmp;
        }
        ListNode* ret = res->next;
        delete res;
        return ret;
    }     
};

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

BM3 链表中的节点每k个一组翻转

描述

将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表
如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样
你不能更改节点中的值，只能更改节点本身。

数据范围： 0≤n≤2000,1≤k≤2000 ，链表中每个元素都满足 0≤val≤1000
要求空间复杂度 O(1)，时间复杂度 O(n)

例如：

给定的链表是 1→2→3→4→5

对于 k=2 , 你应该返回 2→1→4→3→5

对于 k=3k=3 , 你应该返回 3→2→1→4→5

题解：

分组反转的第一步肯定是分段，至少分成一组一组的才能够进行反转。组内反转之后再进行分组之间的链接。

链表一组中的第一个元素反转之后跑到组内的最后一个元素了，那么我们返回的时候返回的应该是第一组原来的末尾元素。原本的链表首部在反转之后要链接下一组反转后的首部。从前往后处理太麻烦。

我们可以：从最后一组开始反转，可以得到最后一组的链表首，从而直接连接到倒数第二个组反转后的尾部之后。

从后往前进行反转的方法是递归，或者说是栈。我们可以递归，因为如果我们把第一个分组反转，那么剩余的n-1 组反转后的结果接到第一组后面就可以了，剩余的n-1 就是子问题，可以无限拆分成一次。

具体做法：

• step 1：每次从进入函数的头节点优先遍历链表k次（遍历时找到尾），分出一组，若是后续不足k个节点，不用反转直接返回头。
• step 2：从进入函数的头节点开始，依次反转接下来的一组链表，反转过程同BM1.反转链表。
• step 3：这一组经过反转后，原来的头变成了尾，后面接下一组的反转结果，下一组采用上述递归继续。

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* reverseKGroup(ListNode* head, int k) {
        // write code here
        ListNode* tail = head;
        //遍历k遍找到尾，如果没有k次就已经到nullptr了，说明链表遍历完了，返回头
        for(int i = 0; i < k;++i){
            if(tail == nullptr) return head;
            tail = tail->next;
        }
        //have found the tail
        //反转这组链表
        ListNode* prev = nullptr;
        ListNode* cur = head;
        while(cur != tail){
            ListNode* tmp = cur->next;
            cur->next = prev;
            prev = cur;
            cur = tmp;
        }
        //继续反转下一组，递归进行。
        head->next = reverseKGroup(tail, k);
        //返回原来的头。
        return prev;
    }
};
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

BM4 合并两个排序的链表

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。

数据范围： 0≤n≤10000，−1000≤节点值≤1000
要求：空间复杂度 O(1)，时间复杂度 O(n)

题解：

第一种比较简单的做法就是递归。因为这是很典型的可以递归的程序，就是可以拆分出子问题，然后不断拆分最后拆分成一个的情景。

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
	if(pHead1 == nullptr) return pHead2;
	if(pHead2 == nullptr) return pHead1;
	if(pHead1->val <= pHead2->val){
		pHead1->next = Merge(pHead1->next, pHead2);
		return pHead1;
	}else{
		pHead2->next = Merge(pHead1,pHead2->next);
		return pHead2;
	}
	}
};

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

复杂度分析：

• 时间复杂度：O(n)O(n)，最坏相当于遍历两个链表每个结点一次
• 空间复杂度：O(n)O(n)，递归栈长度最大为nn

第二种方法：迭代

可以新建一个空表头，然后后面链接两个链表排序后的节点。首先遍历两个链表不为空的情况，取较小值添加在新的链表后面，每次只把被添加的链表的指针后移，后面如果有一个链表为空，一个链表有剩余的节点，他们的值将大于前面的所有的值，这时候我们直接连载新的链表后面即可。

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
	if(pHead1 == nullptr) return pHead2;
	if(pHead2 == nullptr) return pHead1;
	ListNode* ptr1 = pHead1;
	ListNode* ptr2 = pHead2;
	ListNode* res = ptr1->val <= ptr2->val ? ptr1 : ptr2;
	ListNode* head = new ListNode(-1);
	while(ptr1 && ptr2){
		if(ptr1->val <= ptr2->val){
			head->next = ptr1;
			ptr1 = ptr1->next;
		}else{
			head->next = ptr2;
			ptr2 = ptr2->next;
		}
		head = head->next;
	}
	//ptr1走完了
	if(ptr1 == nullptr){
		head->next = ptr2;
	}else{
		head->next = ptr1;
	}
	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

BM5 合并k个已排序的链表

描述

合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。

数据范围：节点总数 0≤n≤5000，每个节点的val满足 ∣val∣<=1000

要求：时间复杂度 O(nlogn)

题目的主要信息：

• 给定k个排好序的升序链表
• 将这k个链表合并成一个大的升序链表，并返回这个升序链表的头

方法1:归并排序

归并排序简单讲就是一个数组每次划分成等长的两部分，对两部分分别进行排序就是子问题。对子问题继续划分，直到子问题只有一个元素。随后进行还原，将每个子问题和相邻的另一个子问题利用双指针的方式，一个与一个进行合并成两个，两个和两个合并成4个，每个单独的子问题合并都是有序的，所以最终结果总体有序。

在这个题目里，我们要做的就是首先把这个lists分成很多个只有一个元素的子问题（使用了divideMerge 函数），在divideMerge 函数内部调用了Merge 函数，而Merge 函数内部又会调用divideMerge 函数。结果就是分成了一个个的单个元素的链表，然后Merge 合并起来。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
  public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        //一个已经为空了，直接返回另一个
        if (pHead1 == NULL) return pHead2;
        if (pHead2 == NULL) return pHead1;
        //加一个表头
        ListNode* head = new ListNode(0);
        ListNode* cur = head;
        //两个链表都要不为空
        while (pHead1 && pHead2) {
            //取较小值的节点
            if (pHead1->val <= pHead2->val) {
                cur->next = pHead1;
                //只移动取值的指针
                pHead1 = pHead1->next;
            } else {
                cur->next = pHead2;
                //只移动取值的指针
                pHead2 = pHead2->next;
            }
            //指针后移
            cur = cur->next;
        }
        //哪个链表还有剩，直接连在后面
        if (pHead1)
            cur->next = pHead1;
        else
            cur->next = pHead2;
        //返回值去掉表头
        return head->next;
    }
    ListNode* divideMerge(vector<ListNode*>& lists, int left, int right) {
        if (left > right)    return nullptr;
        else if (left == right) return lists[left];
        int mid = left + (right - left) / 2;
        return Merge(divideMerge(lists, left, mid), divideMerge(lists, mid + 1, right));
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return divideMerge(lists, 0, lists.size() - 1);
    }
};
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

BM6 判断链表是否有环

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

思路：快慢指针，快指针一次走两步，慢指针一次走一步，如果没环，快指针会先走到链表尾，如果有环，快指针会先入环，而后慢指针入环，因为二者步幅差1，所以最终一定会相遇。

我的解法：

/**
 * 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 || !head->next) return false; //如果头节点和头节点的下一个是空，那么肯定不会成环
        ListNode* fast = head->next;
        ListNode* slow = head;
        while(fast){
            if(fast == slow){
                return true;
            }
            if(fast->next){
                fast = fast->next->next;
            }else{ return false; }
            slow = slow->next;
        }
        return false;
    }
};
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

BM7 链表中环的入口结点

描述

给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。

数据范围： n≤10000，1<=结点值<=10000

要求：空间复杂度 O(1)，时间复杂度 O(n)

环的题目中，我们知道如何判断是否有环（快慢指针），那么同样的，入口结点也可以用快慢指针解决。只需要：

• 让快慢指针从链表头出发，快2慢1，如果有环最终必会相遇（这也是判断是否有环的方法）
• 将快指针回调回链表头，开始快慢都每次各走一步，相遇点即为入口结点。

下面是证明方法：

假设有环，环外长度为a，相遇时fast 和slow 共同走过的环内的长度为b，此时 slow剩余没走过的环长为c

fast = a + b + n * (b + c);
slow = a + b;

同时，fast = 2 slow; --> a = (n - 1)b + n * c;

所以如果让 fast 置为链表头，一次走一步，走 a 长度的，那么 slow 也会走 a 长度，因为 a = (n - 1)b + n * c，因为slow 原本在 a + b 位置， 所以相加，正好得到： a + a + b = (n - 1)b + n * c + a + b = a + n (b + c); 所以恰好会在链表环入口处相遇。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        ListNode* fast = pHead;
        ListNode* slow = pHead;
        while(fast){
            slow = slow->next;
            if(fast->next) fast = fast->next->next;
            else return nullptr;
            if(fast == slow){
                fast = pHead;
                while(fast != slow){
                    fast = fast->next;
                    slow = slow->next;
                }
                return fast;
            }
        }
        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

BM8 链表中倒数第k个结点

描述

输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。

如果该链表长度小于k，请返回一个长度为 0 的链表。

我们如果想要找到倒数第k个结点，可以双指针法，让快指针先走到第k个位置，接下来，慢指针和快指针一起走，那么快指针走到头的时候，慢指针刚好走到倒数第k个结点。

class Solution {
public:
 /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pHead ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        // write code here
        if(!pHead || k <= 0) return nullptr;
        ListNode* pfast = pHead;
        ListNode* pslow = pHead;
        for(int i = k; i > 0; --i){
            if(pfast) pfast = pfast->next;
            else if(!pfast && i == 0) return pHead;
            else return nullptr;
        }
        while(pfast){
            pfast = pfast->next, pslow = pslow->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
23
24
25
26
27

BM9 删除链表的倒数第n个结点

描述

给定一个链表，删除链表的倒数第 n 个节点并返回链表的头指针
例如， 给出的链表为: 1→2→3→4→5, n*=2.
删除了链表的倒数第 n*之后,链表变为1→2→3→5

数据范围： 链表长度 0≤n≤1000，链表中任意节点的值满足 0≤val≤100

要求：空间复杂度 O(1)，时间复杂度 O(n)
备注： 题目保证 n 一定是有效的

其实就是在上面BM8的基础上添加了删除结点的操作，要删除这个结点，我们在找到这个结点之后（BM8），必须要保存这个结点前面的结点，然后修改其指向即可。

class Solution {
public:

    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* prehead = new ListNode(-1);
        prehead->next = head;
        ListNode* fast = head;
        ListNode* slow = head;
        ListNode* prevslow = prehead;
        while(n--) fast = fast->next;
        while(fast)
        {
            fast = fast->next;
            prevslow = slow;
            slow = slow->next;
        }
        prevslow->next = slow->next;
        slow->next = nullptr;
        delete slow;

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

BM10 两个链表的第一个公共结点

思路：我们可以采用简单的双指针法，可以假设A 长度为m， B 长度为n，如果相交，A 和 B相交片段长度为 x， 不相交的片段长度分别为a 和b。

那么如果我们采用双指针法：

当链表 headA 和 headB 都不为空时，创建两个指针 pA和 pB，初始时分别指向两个链表的头节点 headA 和 headB，然后将两个指针依次遍历两个链表的每个节点。具体做法如下：

• 每步操作需要同时更新指针 pA 和 pB。
• 如果指针 pA不为空，则将指针 pA 移到下一个节点；如果指针 pB不为空，则将指针 pB 移到下一个节点。
• 如果指针 pA为空，则将指针 pA 移到链表 headB的头节点；如果指针 pB 为空，则将指针 pB 移到链表 headA 的头节点。
• 当指针 pA 和 pB 指向同一个节点或者都为空时，返回它们指向的节点或者 null。

那么如果二者相交，则 m = a + x， n = b + x。pA 和 pB 一定在走过 a + b + x 长度时相等。如果二者不相交，则一定不会出现相等（可以分类讨论）。

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
		if(!pHead1 || !pHead2) return nullptr;
        ListNode* pA = pHead1;
		ListNode* pB = pHead2;
		while(pA != pB){
			if(pA == nullptr) pA = pHead2;
			else pA = pA->next;
			if(pB == nullptr) pB = pHead1;
			else pB = pB->next;
		}
		if(pA == nullptr) return nullptr;
		else return pA;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

BM11 链表相加(2)

描述

假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。

给定两个这种链表，请生成代表两个整数相加值的结果链表。

数据范围：0≤n,m≤1000000，链表任意值 0≤val≤9
要求：空间复杂度 O(n)，时间复杂度 O(n)

例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。

思路：我们看 937 和 63的例子，如果我们想进行加法操作，要从个位开始，所以我们考虑先把链表反转过来，然后进行加法，加法分两步，一步是建立新节点，结点的val 应该在0 - 9之间，还有一步是计算进位，进位会累积到下一位计算。要注意的是，我们在最后head1 和 head2 都为空的时候，需要检查一下pro 是否为0，如果不为零，代表有进位，我们需要加一个结点，值为1.

class Solution {
public:
    ListNode* reverseList(ListNode* head)
    {
        if(!head) return nullptr;
        ListNode* prev = nullptr;
        ListNode* cur = head;
        while(cur)
        {
            ListNode* next = cur->next;
            cur->next = prev;

            prev = cur;
            cur = next;
        }
        return prev;
    }
  
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        if(!head2) return head1;
        if(!head1) return head2;
        head1 = reverseList(head1);
        head2 = reverseList(head2);
        ListNode* prehead = new ListNode(-1);
        ListNode* node = prehead;
        int pro = 0;
        while(head1 || head2)
        {

            int sum = (head1 ? head1->val : 0) + (head2 ? head2->val : 0) + pro;
            pro = sum / 10;
            ListNode* cur = new ListNode(sum % 10);
            node->next = cur;
            node = cur;

            if(head1) head1 = head1->next;
            if(head2) head2 = head2->next;
        }
        if(pro) node->next = new ListNode(1);
        return reverseList(prehead->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

BM12 单链表的排序

解法1: 使用辅助数组进行排序，首先遍历链表将元素依次填入数组，对数组进行排序，再遍历数组进行元素回填。

在这里我手写了heapsort 顺便复习一下。

class Solution {
  public:
    void heapify(int n, int len, vector<int>& nums) {
        int lson = 2 * n + 1;
        int rson = 2 * n + 2;
        int maxi = n;
        if (lson <= len - 1 && nums[maxi] < nums[lson]) maxi = lson;
        if (rson <= len - 1 && nums[maxi] < nums[rson]) maxi = rson;
        if (maxi != n) {
            swap(nums[maxi], nums[n]);
            heapify(maxi, len, nums);
        }
    }
    void heapSort(vector<int>& nums) {
        int len = nums.size();
        for (int i = (len - 1) / 2; i >= 0; --i) heapify(i, len, nums); //建堆
        for (int i = len - 1; i >= 0; --i) {
            swap(nums[i], nums[0]);
            heapify(0, --len, nums);
        }
    }
    ListNode* sortInList(ListNode* head) {
        ListNode* prehead = new ListNode(-1);
        prehead->next = head;

        vector<int> v;
        while(head)
        {
            v.push_back(head->val);
            head = head->next;
        }
        heapSort(v);
        head = prehead->next;
        for(int i = 0; i < v.size(); ++i)
        {
            head->val = v[i];
            head = head->next;
        }
        return prehead->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

解法2: 归并排序（递归）

主要通过递归实现链表归并排序，有以下两个环节：

1、分割 cut 环节： 找到当前链表中点，并从中点将链表断开（以便在下次递归 cut 时，链表片段拥有正确边界）；

使用 fast,slow 快慢双指针法，奇数个节点找到中点，偶数个节点找到中心左边的节点。
找到中点 slow 后，执行 slow.next = None 将链表切断。
递归分割时，输入当前链表左端点 head 和中心节点 slow 的下一个节点 tmp(因为链表是从 slow 切断的)。
cut 递归终止条件： 当head->next == nullptr时，说明只有一个节点了，直接返回此节点

2、合并 merge 环节： 将两个排序链表合并，转化为一个排序链表。
双指针法合并，建立辅助哨兵头节点作为头部。
设置两指针 left, right 分别指向两链表头部，比较两指针处节点值大小，由小到大加入合并链表头部，指针交替前进，直至添加完两个链表。
返回辅助哨兵位的下一位。
时间复杂度 O(l + r)，l, r 分别代表两个链表长度。
3、特殊情况，当题目输入的 head == nullptr 时，直接返回head (nullptr)。

时间复杂度O(NlogN)：N表示链表结点数量，二分归并算法O(NlogN)

空间复杂度O(1)：仅使用常数级变量空间

class Solution {
public:
    ListNode* sortInList(ListNode* head) {

        //处理特殊情况 !head 
        //处理递归终止条件 !head->next
        if(!head || !head->next) return head;
        //1. 应用递归应该找中点
        //快慢指针法找到中点
        ListNode* fast = head->next;
        ListNode* slow = head;
        while(fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }

        ListNode* mid = slow;
        //2. 左右区间分别调用函数，注意区间要断开。
        ListNode* midBegin = slow->next;
        slow->next = nullptr;

        ListNode* left = sortInList(head);
        ListNode* right = sortInList(midBegin);

        //3. 新链表的创建(合并),常规双指针合并。
        ListNode* prehead = new ListNode(-1);
        ListNode* cur = prehead;
        while(left && right)
        {
            if(left->val < right->val)
            {
                cur->next = left;
                left = left->next;
            }
            else
            {
                cur->next = right;
                right = right->next;
            }
            cur = cur->next;
        }
        cur->next = ((left != nullptr) ? left : right);
        return prehead->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

BM13 判断一个链表是否为回文结构

描述:

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

测试样例：

1->2->2->1
返回：true
1
2

思路：首先找到中间结点；将中间结点后半部分倒置；分别从头结点和尾结点向中间遍历，检测在达到中间时刻之间val的值是否都相等。所以我们需要用上之前写的题目，先找到中间结点，然后从中间结点开始逆置，就会形成如下的形状。

1 -> 2 -> 3 <- 2 <- 1
1

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
  public:
    struct ListNode* middleNode(struct ListNode* head) {
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        struct ListNode* fast = dummy;
        struct ListNode* slow = dummy;
        while (fast) {
            slow = slow->next;
            if (fast->next)
                fast = fast->next->next;
            else
                return slow;
        }
        return slow;
    }
    struct ListNode* reverseList(struct ListNode* head) {
        struct ListNode* cur = head;
        struct ListNode* pre = nullptr;
        struct ListNode* next = nullptr;
        while (cur) {
            next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
    bool chkPalindrome(ListNode* A) {
        ListNode* midNode = middleNode(A);
        ListNode* tailNode = reverseList(midNode);
        while(A != midNode){
            if(A->val != tailNode->val) return false;
            A = A->next;
            tailNode = tailNode->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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

BM14 链表的奇偶重排

具体做法：

• step 1：判断空链表的情况，如果链表为空，不用重排。
• step 2：使用双指针odd和even分别遍历奇数节点和偶数节点，并给偶数节点链表一个头。
• step 3：上述过程，每次遍历两个节点，且even在后面，因此每轮循环用even检查后两个元素是否为NULL，如果不为再进入循环进行上述连接过程。
• step 4：将偶数节点头接在奇数最后一个节点后，再返回头部。

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
      //  如果head 空 或者 链表只有一个元素，可以直接返回不用重排
	      if(!head || !head->next) return head;
      	//设置偶数的链表头，一会连接时用
        ListNode* evenhead = head->next;
      	//双指针遍历修改数组，因为偶数在奇数之后，判空偶数。
        ListNode* even = evenhead;
        ListNode* odd = head;
        while(even && even->next)
        {
            odd->next = even->next;
            odd = odd->next;
            even->next = odd->next;
            even = even->next;
        }
      	//连接链表
        odd->next = evenhead;
        return head;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

BM15 删除有序链表中重复的元素1

描述

删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次
例如：
给出的链表为1→1→2,返回1→2.
给出的链表为1→1→2→3→3,返回1→2→3

数据范围：链表长度满足 0≤n≤100，链表中任意节点的值满足 ∣val∣≤100

进阶：空间复杂度 O(1)，时间复杂度 O(n)

使用双指针求解，一个指向前面prev，一个指向后面cur，对二者的值进行比较，如果相等则删除后面节点，操作为前面的指针prev指向cur之后的结点，再置空cur 的指向。

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        // write code here
        if(!head || !head->next) return head;
        ListNode* prev = head;
        ListNode* cur = head->next;
        while(cur)
        {
            if(prev->val == cur->val)
            {
                prev->next = cur->next;
                cur->next = nullptr;
                delete cur; 
                cur = prev->next;
            }else
            {
                prev = cur;
                cur = cur->next;
            }
        }
        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

BM16 删除有序链表中重复的元素(2)

描述

给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。
例如：
给出的链表为1→2→3→3→4→4→5, 返回1→2→5.
给出的链表为1→1→1→2→3, 返回2→3.

数据范围：链表长度 0≤n≤10000，链表中的值满足 ∣val∣≤1000

要求：空间复杂度 O(n)，时间复杂度 O(n)

进阶：空间复杂度 O(1)，时间复杂度 O(n)

这是一个升序链表，重复的节点都连在一起，我们就可以很轻易地比较到重复的节点，然后将所有的连续相同的节点都跳过，连接不相同的第一个节点。

具体做法：

• step 1：给链表前加上表头，方便可能的话删除第一个节点。

• step 2：遍历链表，每次比较相邻两个节点，如果遇到了两个相邻节点相同，则新开内循环将这一段所有的相同都遍历过去。

• step 3：在step 2中这一连串相同的节点前的节点直接连上后续第一个不相同值的节点。

• step 4：返回时去掉添加的表头。

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head || !head->next) return head;//判断特殊情况

        ListNode* prehead = new ListNode(-1); //哨兵头节点
        prehead->next = head;
        ListNode* cur = prehead; 
        while(cur->next && cur->next->next) //判断下一位和下下一位是否相等
        {
          	//如果相等 进入循环剔除这些结点
            if(cur->next->val == cur->next->next->val)
            {
                int tmpVal = cur->next->val;
                while(cur->next && cur->next->val == tmpVal) cur->next = cur->next->next;
            }
            else cur = cur->next;
        }
        return prehead->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21