凡人多烦事01

这个屌丝很懒，什么也没留下！

热门标签

【数据结构与算法-链表经典例题汇总】

作者：凡人多烦事01 | 2024-04-17 10:47:22

踩

【数据结构与算法-链表经典例题汇总】

典例1、链表逆序-a（easy）

题目描述：
思路：依次遍历链表的节点，每遍历一个节点就逆置一个节点 。

在这里插入图片描述

LeetCode提交OJ测试链接:
OJ测试代码实现：

class Solution {
public:
    ListNode* reverseList(ListNode* head) { //链表头结点指针
        ListNode *new_head = NULL;  // 返回链表逆序后的头结点指针
		while(head){
			ListNode *next = head->next;  // 备份
			head->next = new_head;   // 更新指向
			new_head = head;   // 移动new_head
			head = next;      //  移动head ，遍历链表各个节点
		}
		return new_head;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

完整的本地代码：

#include <stdio.h>

struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* reverseList(ListNode* head) { //链表头结点指针
        ListNode *new_head = NULL;  // 返回链表逆序后的头结点指针
		while(head){
			ListNode *next = head->next;  // 备份
			head->next = new_head;   // 更新指向
			new_head = head;   // 移动new_head
			head = next;      //  移动head ，遍历链表各个节点
		}
		return new_head;
    }
};

int main(){	
	ListNode a(1);
	ListNode b(2);
	ListNode c(3);
	ListNode d(4);
	ListNode e(5);
	a.next = &b;
	b.next = &c;
	c.next = &d;
	d.next = &e;
	Solution solve;	
	ListNode *head = &a;
	printf("Before reverse:\n");
	while(head){
		printf("%d\n", head->val);
		head = head->next;
	}
	head = solve.reverseList(&a);
	printf("After reverse:\n");
	while(head){
		printf("%d\n", head->val);
		head = head->next;
	}
	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
36
37
38
39
40
41
42
43
44
45
46
47
48

典例1、链表逆序-b（medium）

同LeetCode-92-medium（中等）
题目描述：
思路：对关键的节点位置进行改变节点的连接顺序，同时注意节点的备份
1、找到特殊的节点，进行备份；
2、计算逆置要求的节点个数（可用上述的简单顺序链表的逆序逻辑）；
3、对更改后的节点进行重新连接；
4、考虑特殊的情况；

在这里插入图片描述

LeetCode提交OJ测试链接.
OJ测试提交代码：

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {

        int reverse_num=right- left +1 ; //  计算需要逆置的节点个数
        ListNode* pre_head = nullptr;   // 初始化开始逆置的节点的前驱
        ListNode* result =  head;     // 最后转换后的链表头结点，非特殊情况即为head

        while(head && --left ){ // 将head 向前移动m-1个位置，找到需要逆置部分的第一个节点
            pre_head = head;// 记录head的前驱
            head = head->next;// 向后移动一个节点位置
        }
        ListNode *modify_list_tail = head; // 将 modify_list_tail 指向当前的 head，就是逆置部分的链表尾部
        // 开始逆置 reverse_num 个节点
        ListNode* new_head =  nullptr;     // 声明一个临时的头结点，用于逆置
        while(head && reverse_num){
            ListNode* next = head->next; // 备份当前节点的指向（指针域） 
            head->next = new_head;  // 修改节点的指向
            new_head = head;    // 移动 new_head 的位置
            head = next;       //  更新 head
            reverse_num--; // 
        }
        modify_list_tail->next = head;// 连接逆置后的链表尾 与 逆置段的后一个节点
        if (pre_head){// 如果pre_head 不空，说明不是从第一个节点开始逆置的，left > 1
            pre_head->next = new_head;// 将逆置链表开始的节点前驱与逆置后的头结点连接
        }
        else{// 如果pre_head 空，说明是从第一个节点开始逆置的，left==1
            result = new_head;// 结果就是逆置后的头结点
        }
        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
30
31
32
33

可本地运行的完整代码：

#include <stdio.h>

struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        int change_len = n - m + 1;
        ListNode *pre_head = NULL;
        ListNode *result = head;
        while(head && --m){
        	pre_head = head;
        	head = head->next;
        }
        ListNode *modify_list_tail = head;
        
        ListNode *new_head = NULL;
		while(head && change_len){
			ListNode *next = head->next;
			head->next = new_head;
			new_head = head;
			head = next;
			change_len--;
		}
		modify_list_tail->next = head;
		
		if (pre_head){
			pre_head->next = new_head;
		}
		else{
			result = new_head;
		}
		return result;
    }
};

int main(){	
	ListNode a(1);
	ListNode b(2);
	ListNode c(3);
	ListNode d(4);
	ListNode e(5);
	a.next = &b;
	b.next = &c;
	c.next = &d;
	d.next = &e;
	Solution solve;
	ListNode *head = solve.reverseBetween(&a, 2, 4);	
	while(head){
		printf("%d\n", head->val);
		head = head->next;
	}
	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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

典例2、求两个链表的交点-（easy）

同LeetCode-160（简单）
题目描述：
思路：
方法1： STL - set 使用（set 无重复的元素）
使用set 求交集：
LeetCode提交OJ测试链接.
OJ测试提交代码：

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
   		std::set<ListNode*> node_set;
		while(headA){
			node_set.insert(headA);
			headA = headA->next;
        }
        while(headB){
        	if (node_set.find(headB) != node_set.end()){
	        	return headB;
	        }
	        headB = headB->next;
        }
        return NULL;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

本地可执行的代码：


#include <stdio.h>

struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};

#include <set>

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
   		std::set<ListNode*> node_set;
		while(headA){
			node_set.insert(headA);
			headA = headA->next;
        }
        while(headB){
        	if (node_set.find(headB) != node_set.end()){
	        	return headB;
	        }
	        headB = headB->next;
        }
        return NULL;
    }
};

int main(){
	ListNode a1(1);
	ListNode a2(2);
	ListNode b1(3);
	ListNode b2(4);
	ListNode b3(5);
	ListNode c1(6);
	ListNode c2(7);
	ListNode c3(8);
	a1.next = &a2;
	a2.next = &c1;
	c1.next = &c2;
	c2.next = &c3;
	b1.next = &b2;
	b2.next = &b3;
	b3.next = &c1;
	
	Solution solve;
	ListNode *result = solve.getIntersectionNode(&a1, &b1);
	printf("%d\n", result->val);
	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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

思路2：（最优）分别计算连个链表的长度，计算较长的链表多出来的长度，移动较长的长度差与短链表指针对其，再同时移动，直到指针指向同一个节点时，返回交点。

在这里插入图片描述

OJ提交代码：
C++

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
   		int list_A_len = get_list_length(headA);
   		int list_B_len = get_list_length(headB);   		
   		if (list_A_len > list_B_len){
   			headA = forward_long_list(list_A_len, list_B_len, headA);
	   	}
	   	else{
	   		headB = forward_long_list(list_B_len, list_A_len, headB);
	   	}   		
        while(headA && headB){
        	if (headA == headB){
	        	return headA;
	        }
	        headA = headA->next;
	        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

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
######方法1：集合法
        # temp= set()
        # while headA:
        #     temp.add(headA)
        #     headA = headA.next
        # while headB:
        #     if headB in temp:
        #         return headB
        #     headB = headB.next
        # return None

#####方法2：移动对齐，再同步移动

        len_A = self.get_list_node(headA)
        len_B = self.get_list_node(headB)

        if len_A>len_B:
            headA = self.forward_long_node(len_A,len_B,headA)
        else:
            headB = self.forward_long_node(len_B,len_A,headB)

        while headA and headB:
            if headA == headB:
                return headA
            headA = headA.next
            headB = headB.next

        return None

    def forward_long_node(self,long_len,short_len,head):
        forward_step = long_len-short_len
        while head and forward_step:
            head = head.next
            forward_step -= 1
        return head

    def get_list_node(self,head):
        len = 0
        while head:
            len += 1
            head = head.next
        return len
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

可本地运行的完整代码：


#include <stdio.h>

struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};

int get_list_length(ListNode *head){
	int len = 0;
	while(head){
		len++;
		head = head->next;
	}
	return len;
}

ListNode *forward_long_list(int long_len, 
				int short_len, ListNode *head){
	int delta = long_len - short_len;
	while(head && delta){
		head = head->next;
		delta--;
	}
	return head;
}

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
   		int list_A_len = get_list_length(headA);
   		int list_B_len = get_list_length(headB);   		
   		if (list_A_len > list_B_len){
   			headA = forward_long_list(list_A_len, list_B_len, headA);
	   	}
	   	else{
	   		headB = forward_long_list(list_B_len, list_A_len, headB);
	   	}   		
        while(headA && headB){
        	if (headA == headB){
	        	return headA;
	        }
	        headA = headA->next;
	        headB = headB->next;
        }
        return NULL;
    }
};

int main(){
	ListNode a1(1);
	ListNode a2(2);
	ListNode b1(3);
	ListNode b2(4);
	ListNode b3(5);
	ListNode c1(6);
	ListNode c2(7);
	ListNode c3(8);
	a1.next = &a2;
	a2.next = &c1;
	c1.next = &c2;
	c2.next = &c3;
	b1.next = &b2;
	b2.next = &b3;
	b3.next = &c1;	
	Solution solve;
	ListNode *result = solve.getIntersectionNode(&a1, &b1);
	printf("%d\n", result->val);
	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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

典例3、链表求环 - （medium）

题目描述：
思路1：使用STL - set 集合
LeetCode提交OJ测试链接.
OJ测试提交代码：

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        std::set<ListNode *> node_set;
        while(head){
        	if (node_set.find(head) != node_set.end()){
	        	return head;
	        }
	        node_set.insert(head);
        	head = head->next;
        }
        return NULL;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

可本地运行的代码参考：


#include <stdio.h>
struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};

#include <set>
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        std::set<ListNode *> node_set;
        while(head){
        	if (node_set.find(head) != node_set.end()){
	        	return head;
	        }
	        node_set.insert(head);
        	head = head->next;
        }
        return NULL;
    }
};

int main(){
	ListNode a(1);
	ListNode b(2);
	ListNode c(3);
	ListNode d(4);
	ListNode e(5);
	ListNode f(6);
	a.next = &b;
	b.next = &c;
	c.next = &d;
	d.next = &e;
	e.next = &f;
	//f.next = &c;
	Solution solve;
	ListNode *node = solve.detectCycle(&a);
	if (node){
		printf("%d\n", node->val);
	}
	else{
		printf("NULL\n");
	}
	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
36
37
38
39
40
41
42
43
44
45
46
47
48

思路2：快慢指针
利用结论：从 head 与 meet 出发，两指针速度一样，相遇点就是环的起点。

在这里插入图片描述

LeetCode提交OJ测试链接.
OJ测试提交代码：

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
    	ListNode *fast = head;
    	ListNode *slow = head;
    	ListNode *meet = NULL;
    	while(fast){
    		slow = slow->next;
    		fast = fast->next;
    		if (!fast){
		    	return NULL;
		    }
		    fast = fast->next;
		    if (fast == slow){
    			meet = fast;
    			break;
    		}
	    }
	    if (meet == NULL){
    		return NULL;
    	}
    	while(head && meet){
	    	if (head == meet){
	    		return head;
	    	}
	    	head = head->next;
	    	meet = meet->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
24
25
26
27
28
29
30
31
32

可本地运行的完整代码：


#include <stdio.h>

struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
    	ListNode *fast = head;
    	ListNode *slow = head;
    	ListNode *meet = NULL;
    	while(fast){
    		slow = slow->next;
    		fast = fast->next;
    		if (!fast){
		    	return NULL;
		    }
		    fast = fast->next;
		    if (fast == slow){
    			meet = fast;
    			break;
    		}
	    }
	    if (meet == NULL){
    		return NULL;
    	}
    	while(head && meet){
	    	if (head == meet){
	    		return head;
	    	}
	    	head = head->next;
	    	meet = meet->next;
	    }
        return NULL;
    }
};

int main(){
	ListNode a(1);
	ListNode b(2);
	ListNode c(3);
	ListNode d(4);
	ListNode e(5);
	ListNode f(6);
	ListNode g(7);
	a.next = &b;
	b.next = &c;
	c.next = &d;
	d.next = &e;
	e.next = &f;
	f.next = &g;
	g.next = &c;
	Solution solve;
	ListNode *node = solve.detectCycle(&a);
	if (node){
		printf("%d\n", node->val);
	}
	else{
		printf("NULL\n");
	}
	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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

典例4、链表划分- (medium)

题目描述：
思路：巧用临时头结点
遍历所有节点；
借助两个临时头节点： less_head 、 more_head
分别插入不同的两个节点的后面；
然后，更改两个暂时链表的连接方向；
置空连接后最后一个节点的控制域；
返回值：less_head->next

在这里插入图片描述

LeetCode提交OJ测试链接.
OJ测试提交代码：

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
    	ListNode less_head(0);
    	ListNode more_head(0);
    	ListNode *less_ptr = &less_head;
    	ListNode *more_ptr = &more_head;
        while(head){
        	if (head->val < x){
        		less_ptr->next = head;
        		less_ptr = head;
			}
			else {
				more_ptr->next = head;
				more_ptr = head;
			}
        	head = head->next;
        }
        less_ptr->next = more_head.next;
        more_ptr->next = NULL;
        return less_head.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

可本地运行的完整代码：


#include <stdio.h>
	
struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
    	ListNode less_head(0);
    	ListNode more_head(0);
    	ListNode *less_ptr = &less_head;
    	ListNode *more_ptr = &more_head;
        while(head){
        	if (head->val < x){
        		less_ptr->next = head;
        		less_ptr = head;
			}
			else {
				more_ptr->next = head;
				more_ptr = head;
			}
        	head = head->next;
        }
        less_ptr->next = more_head.next;
        more_ptr->next = NULL;
        return less_head.next;
    }
};

int main(){
	ListNode a(1);
	ListNode b(4);
	ListNode c(3);
	ListNode d(2);
	ListNode e(5);
	ListNode f(2);
	a.next = &b;
	b.next = &c;
	c.next = &d;
	d.next = &e;
	e.next = &f;	
	Solution solve;
	ListNode *head = solve.partition(&a, 3);	
	while(head){
		printf("%d\n", head->val);
		head = head->next;
	}
	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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

典例5、复杂链表的深度拷贝 - (hard)

题目描述：
思路：节点地址与节点序号对应（STL-map）
难点：拷贝后的链表，仍有random指针特点
深度拷贝，生成的新链表节点的指针地址与之前对应顺序的节点不一样；
旧链表中，需要记录每一个节点的random节点指向的是哪一个节点；新链表中，每一个节点对应的新的节点地址；2个map

在这里插入图片描述

LeetCode提交OJ测试链接.
OJ测试提交代码：

class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
    	std::map<RandomListNode *, int> node_map;
    	std::vector<RandomListNode *> node_vec;
    	RandomListNode *ptr = head;
    	int i = 0;
    	while (ptr){
	    	node_vec.push_back(new RandomListNode(ptr->label));
	    	node_map[ptr] = i;
	    	ptr = ptr->next;
	    	i++;
	    }
	    node_vec.push_back(0);
	    ptr = head;
	    i = 0;
	    while(ptr){
    		node_vec[i]->next = node_vec[i+1];
    		if (ptr->random){
    			int id = node_map[ptr->random];
		    	node_vec[i]->random = node_vec[id];
		    }
    		ptr = ptr->next;
    		i++;
    	}
    	return node_vec[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

可本地运行的完整代码：

	
#include <stdio.h>
		
struct RandomListNode {
	int label;
	RandomListNode *next, *random;
	RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
};

#include <map>
#include <vector>

class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
    	std::map<RandomListNode *, int> node_map;
    	std::vector<RandomListNode *> node_vec;
    	RandomListNode *ptr = head;
    	int i = 0;
    	while (ptr){
	    	node_vec.push_back(new RandomListNode(ptr->label));
	    	node_map[ptr] = i;
	    	ptr = ptr->next;
	    	i++;
	    }
	    node_vec.push_back(0);
	    ptr = head;
	    i = 0;
	    while(ptr){
    		node_vec[i]->next = node_vec[i+1];
    		if (ptr->random){
    			int id = node_map[ptr->random];
		    	node_vec[i]->random = node_vec[id];
		    }
    		ptr = ptr->next;
    		i++;
    	}
    	return node_vec[0];
    }
};

int main(){
	RandomListNode a(1);
	RandomListNode b(2);
	RandomListNode c(3);
	RandomListNode d(4);
	RandomListNode e(5);
	a.next = &b;
	b.next = &c;
	c.next = &d;
	d.next = &e;	
	a.random = &c;
	b.random = &d;
	c.random = &c;
	e.random = &d;	
	Solution solve;
	RandomListNode *head = solve.copyRandomList(&a);	
	while(head){
		printf("label = %d ", head->label);
		if (head->random){
			printf("rand = %d\n", head->random->label);
		}
		else{
			printf("rand = NULL\n");
		}
		head = head->next;
	}
	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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

典例6、排序链表的合并a-两个（easy）

题目描述：

在这里插入图片描述

思路：巧用临时头节点
使用一个临时头节点，由pre指针指向，比较两个链表的头结点数值的大小，将较小的节点插入到pre指针后，并向前移动较小节点对应的指针；
遍历循环比较插入所有的节点；
更改尾部节点的控制域；
返回 pre 指针前的节点；
LeetCode提交OJ测试链接.
OJ测试提交代码：

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    	ListNode temp_head(0);
    	ListNode *pre = &temp_head;
    	while (l1 && l2){
	    	if (l1->val < l2->val){
	    		pre->next = l1;
	    		l1 = l1->next;
	    	}
	    	else{
	    		pre->next = l2;
	    		l2 = l2->next;
	    	}
	    	pre = pre->next;
	    }
	    if (l1){
    		pre->next = l1;
    	}
    	if (l2){
	    	pre->next = l2;
	    }
        return temp_head.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

可本地运行的完整代码：


#include <stdio.h>

struct ListNode {
 	int val; // 数据域
	ListNode *next;  //指针域
	ListNode(int x) : val(x), next(NULL) {}  // 构造函数
};

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    	ListNode temp_head(0);
    	ListNode *pre = &temp_head;
    	while (l1 && l2){
	    	if (l1->val < l2->val){
	    		pre->next = l1;
	    		l1 = l1->next;
	    	}
	    	else{
	    		pre->next = l2;
	    		l2 = l2->next;
	    	}
	    	pre = pre->next;
	    }
	    if (l1){
    		pre->next = l1;
    	}
    	if (l2){
	    	pre->next = l2;
	    }
        return temp_head.next;
    }
};

int main(){
	ListNode a(1);
	ListNode b(4);
	ListNode c(6);
	ListNode d(0);
	ListNode e(5);
	ListNode f(7);
	a.next = &b;
	b.next = &c;
	d.next = &e;
	e.next = &f;
	Solution solve;
	ListNode *head = solve.mergeTwoLists(&a, &d);
	while(head){
		printf("%d\n", head->val);
		head = head->next;
	}
	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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

典例6、排序链表的合并b-多个（hard）

题目描述：
思路1：暴力解法-直接合并 (实际不可取)

在这里插入图片描述

即是答案正确，时间复杂度不符合，超时，pass。
思路2：借助 vector 进行链表头结点排序后相连。
将 K * n 个节点放到 vector 中，再将 vector 排序，再将节点顺序相连。
OJ提交代码：

class Solution {
public:
    ListNode* mergeKLists(std::vector<ListNode*>& lists) {
        std::vector<ListNode *> node_vec;        
        for (int i = 0; i < lists.size(); i++){
        	ListNode *head = lists[i];
        	while(head){
        		node_vec.push_back(head);
	        	head = head->next;
	        }
        }
        if (node_vec.size() == 0){
        	return NULL;
        }        
        std::sort(node_vec.begin(), node_vec.end(), cmp);
        for (int i = 1; i < node_vec.size(); i++){
        	node_vec[i-1]->next = node_vec[i];
        }
        node_vec[node_vec.size()-1]->next = NULL;
        return node_vec[0];
    }
};

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

可本地运行的完整代码：

#include <stdio.h>

struct ListNode {
 	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};

#include <vector>
#include <algorithm>

bool cmp(const ListNode *a, const ListNode *b){
	return a->val < b->val;
}

class Solution {
public:
    ListNode* mergeKLists(std::vector<ListNode*>& lists) {
        std::vector<ListNode *> node_vec;        
        for (int i = 0; i < lists.size(); i++){
        	ListNode *head = lists[i];
        	while(head){
        		node_vec.push_back(head);
	        	head = head->next;
	        }
        }
        if (node_vec.size() == 0){
        	return NULL;
        }        
        std::sort(node_vec.begin(), node_vec.end(), cmp);
        for (int i = 1; i < node_vec.size(); i++){
        	node_vec[i-1]->next = node_vec[i];
        }
        node_vec[node_vec.size()-1]->next = NULL;
        return node_vec[0];
    }
};

int main(){
	ListNode a(1);
	ListNode b(4);
	ListNode c(6);
	ListNode d(0);
	ListNode e(5);
	ListNode f(7);
	ListNode g(2);
	ListNode h(3);
	a.next = &b;
	b.next = &c;	
	d.next = &e;
	e.next = &f;	
	g.next = &h;	
	Solution solve;	
	std::vector<ListNode *> lists;
	lists.push_back(&a);
	lists.push_back(&d);
	lists.push_back(&g);	
	ListNode *head = solve.mergeKLists(lists);
	while(head){
		printf("%d\n", head->val);
		head = head->next;
	}
	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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

思路3：分治后相连（归并），最优解析方法。
对 k 个链表进行分治，两两进行合并。
OJ提交代码：

cpp

class Solution {
public:
	ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    	ListNode temp_head(0);
    	ListNode *pre = &temp_head;
    	while (l1 && l2){
	    	if (l1->val < l2->val){
	    		pre->next = l1;
	    		l1 = l1->next;
	    	}
	    	else{
	    		pre->next = l2;
	    		l2 = l2->next;
	    	}
	    	pre = pre->next;
	    }
	    if (l1){
    		pre->next = l1;
    	}
    	if (l2){
	    	pre->next = l2;
	    }
        return temp_head.next;
    }	
    ListNode* mergeKLists(std::vector<ListNode*>& lists) {
    	if (lists.size() == 0){
        	return NULL;
        }
    	if (lists.size() == 1){
	    	return lists[0];
	    }
	    if (lists.size() == 2){
    		return mergeTwoLists(lists[0], lists[1]);
    	}
    	int mid = lists.size() / 2;
    	std::vector<ListNode*> sub1_lists;
    	std::vector<ListNode*> sub2_lists;
    	for (int i = 0; i < mid; i++){
	    	sub1_lists.push_back(lists[i]);
	    }
	    for (int i = mid; i < lists.size(); i++){
    		sub2_lists.push_back(lists[i]);
    	}
    	ListNode *l1 = mergeKLists(sub1_lists);
    	ListNode *l2 = mergeKLists(sub2_lists);
    	return mergeTwoLists(l1, l2);
    }
};
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

python3

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self,l1,l2):    # 合并两个链表
        pre_ptr = temp_head =ListNode(0)  # 创建一个临时头结点以及指向它的一个指针
        while l1 and l2 : # 两个链表都不空
            if l1.val < l2.val:  # 比较大小依次排在临时节点后面
                pre_ptr.next = l1
                l1 = l1.next
            else:
                pre_ptr.next = l2
                l2 = l2.next
            pre_ptr = pre_ptr.next  # 推进下一个节点   
        if l1:  # 续借 没有 循环完的剩余链表
            pre_ptr.next = l1
        if l2:
            pre_ptr.next = l2
        return temp_head.next  # 返回临时节点的下一个，就是排序好的新链表的头节点
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:   
        if not lists: return None
        # res = None
        # for list_i in lists:
        #     res = self.mergeTwoLists(res,list_i)
        # return res 
        if len(lists) == 1:return lists[0]
        # if len(lists) == 2: return mergeTwoLists(lists[0],lists[1])
        mid = int(len(lists)//2)
        list1 = []
        list2 = []
        for i in range (0,int(len(lists)//2)):
            list1.append(lists[i])
        for i in range (int(len(lists)//2),len(lists)):
            list2.append(lists[i])
    
        return self.mergeTwoLists(self.mergeKLists(list1),self.mergeKLists(list2))
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

可本地运行的完整代码：

#include <stdio.h>

struct ListNode {
 	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};

#include <vector>

class Solution {
public:
	ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    	ListNode temp_head(0);
    	ListNode *pre = &temp_head;
    	while (l1 && l2){
	    	if (l1->val < l2->val){
	    		pre->next = l1;
	    		l1 = l1->next;
	    	}
	    	else{
	    		pre->next = l2;
	    		l2 = l2->next;
	    	}
	    	pre = pre->next;
	    }
	    if (l1){
    		pre->next = l1;
    	}
    	if (l2){
	    	pre->next = l2;
	    }
        return temp_head.next;
    }	
    ListNode* mergeKLists(std::vector<ListNode*>& lists) {
    	if (lists.size() == 0){
        	return NULL;
        }
    	if (lists.size() == 1){
	    	return lists[0];
	    }
	    if (lists.size() == 2){
    		return mergeTwoLists(lists[0], lists[1]);
    	}
    	int mid = lists.size() / 2;
    	std::vector<ListNode*> sub1_lists;
    	std::vector<ListNode*> sub2_lists;
    	for (int i = 0; i < mid; i++){
	    	sub1_lists.push_back(lists[i]);
	    }
	    for (int i = mid; i < lists.size(); i++){
    		sub2_lists.push_back(lists[i]);
    	}
    	ListNode *l1 = mergeKLists(sub1_lists);
    	ListNode *l2 = mergeKLists(sub2_lists);
    	return mergeTwoLists(l1, l2);
    }
};

int main(){
	ListNode a(1);
	ListNode b(4);
	ListNode c(6);
	ListNode d(0);
	ListNode e(5);
	ListNode f(7);
	ListNode g(2);
	ListNode h(3);
	a.next = &b;
	b.next = &c;	
	d.next = &e;
	e.next = &f;	
	g.next = &h;
	Solution solve;	
	std::vector<ListNode *> lists;
	lists.push_back(&a);
	lists.push_back(&d);
	lists.push_back(&g);	
	ListNode *head = solve.mergeKLists(lists);
	while(head){
		printf("%d\n", head->val);
		head = head->next;
	}
	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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

提示：
在理解思路的情况下，自己动手提交；
尝试在纸上写代码，反复练习；
做LeetCode相关链表的其他题目（尝试各个层次）；
关于题面：
听清、看清、对于别人的出题，问问能否给出具体的例子来分析；
冷静分析；
努力解决，不轻易放弃；（起码的思路，局部实现）
保持自信、谦逊的态度；

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/凡人多烦事01/article/detail/439798