刷几道链表题，看看自己对指针的把握程度了

好久不见，这些天和女朋友度假去了，所以也没什么存货，先整一篇吧。

中等题：两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807

  

 

  
1
  
2
  
3
 

示例：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

  

 

  
1
  
2
 

思路：刚开始还会想，把两个链表翻过来再加，后来想了想，还是正着来的好。

只不过是把加一的进位向后了。

代码实现：

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { int flag = 0; int sum = 0; ListNode* temp1 = l1; ListNode* temp2 = l2; ListNode* temp = l1; while(temp1!=NULL && temp2!=NULL){ sum = temp1->val + temp2->val + flag; flag = 0; if(sum>9){ sum-=10; flag = 1; } temp1->val = sum; temp2->val = sum; temp1 = temp1->next; temp2 = temp2->next; } if(temp1!=NULL){ while(temp1->next!=NULL){ if(temp1->val + flag>9){ temp1->val = 0; temp1 = temp1->next; } else{ temp1->val+=flag; flag = 0; break; } } if(flag){ if(temp1->val == 9){ temp1->val = 0; temp1->next = new ListNode(1); } else temp1->val += 1; } return l1; } else if(temp2!=NULL){ while(temp2->next!=NULL){ if(temp2->val + flag>9){ temp2->val = 0; temp2 = temp2->next; } else{ temp2->val+=flag; flag = 0; break; } } if(flag){ if(temp2->val == 9){ temp2->val = 0; temp2->next = new ListNode(1); } else temp2->val += 1; } return l2; } else{ if(flag){ while(temp->next!=NULL) temp = temp->next; temp->next = new ListNode(1); } return l1; } }

  

 

  
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
 

奇偶链表：中等题

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

示例 1:

输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL

  

 

  
1
  
2
 

示例 2:

输入: 2->1->3->5->6->4->7->NULL 
输出: 2->3->6->7->1->5->4->NULL

  

 

  
1
  
2
 

说明:

应当保持奇数节点和偶数节点的相对顺序。
链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。

  

 

  
1
  
2
 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/odd-even-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：
这个题呢，其实思路说难也难，说简单也简单。
手画个图就很清楚了。

我选择维护一个奇链表的尾指针，一个偶链表的尾指针，偶链表尾指针的后一位要么是空，要么就是奇节点。
（画个图就知道）

代码实现：

ListNode* oddEvenList(ListNode* head) { if(head){ ListNode* fast = head->next;  //快指针 ListNode* slow = head;  //慢指针 while (fast && fast->next) { //取出下一个目标节点 /*ListNode* temp = fast->next; temp->next = NULL;*/ //这样写是要出问题的 ListNode* temp = new ListNode(fast->next->val); temp->next = slow->next; //细节，这里不能是fast //将目标节点的位置挤出去 fast->next = fast->next->next; //无缝衔接 slow->next = temp; //快慢指针后移 fast = fast->next; slow = slow->next; //free(temp);   free就报错 } } 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
 

合并K个升序链表：困难题

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
 

示例 2：

输入：lists = []
输出：[]

  

 

  
1
  
2
 

示例 3：

输入：lists = [[]]
输出：[]

  

 

  
1
  
2
 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-k-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码实现：

class Solution {
public: ListNode *mergeKLists(vector<ListNode *> &lists) { int count = lists.size(); if(count == 0){ return NULL; }//if if(count == 1){ return lists[0]; }//if // 链表集合分成两份 vector<ListNode *> leftLists; for(int i = 0;i < count/2;i++){ leftLists.push_back(lists.back()); lists.pop_back(); }//for // 分治 return mergeTwoLists(mergeKLists(leftLists),mergeKLists(lists)); }
private: ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) { ListNode *head = new ListNode(-1); for(ListNode *p = head;l1 != NULL || l2 != NULL;p = p->next){ int val1 = (l1 == NULL) ? INT_MAX : l1->val; int val2 = (l2 == NULL) ? INT_MAX : l2->val; if(val1 <= val2){ p->next = l1; l1 = l1->next; }//if else{ p->next = l2; l2 = l2->next; }//else }//for return head->next; }
};
// 创建链表
ListNode* CreateList(int A[],int n){ ListNode *head = NULL; if(n <= 0){ return head; }//if head = new ListNode(A[0]); ListNode *p1 = head; for(int i = 1;i < n;i++){ ListNode *node = new ListNode(A[i]); p1->next = node; p1 = node; }//for 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
  
48
  
49
  
50
  
51
  
52
 

附赠：数据结构和算法常见面试题大全

文章来源: lion-wu.blog.csdn.net，作者：看，未来，版权归原作者所有，如需转载，请联系作者。

原文链接：lion-wu.blog.csdn.net/article/details/117692573