关于链表中的指针和dummy head

从LeetCode的第21题Merge Two Sorted Lists开始说起

原题表述如下:
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

1
2
3
4
5
6
7
8
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(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
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {

if(NULL == l1) return l2;
if(NULL == l2) return l1;

ListNode* head=NULL; // head of the list to return

// find first element (can use dummy node to put this part inside of the loop)
if(l1->val < l2->val) { head = l1; l1 = l1->next; }
else { head = l2; l2 = l2->next; }

ListNode* p = head; // pointer to form new list

// I use && to remove extra IF from the loop
while(l1 && l2){
if(l1->val < l2->val) { p->next = l1; l1 = l1->next; }
else { p->next = l2; l2 = l2->next; }
p=p->next;
}

// add the rest of the tail, done!
if(l1) p->next=l1;
else p->next=l2;

return head;
}

这种写法最清晰易懂,创建了ListNode head和p两个,head保留不动,这样返回链表的首地址时返回head即可。
`ListNode
p=head;`让p指针的初始地址与head一致,之后p作为之后被操作的指针,与head区分开来。

第二种写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
ListNode dummy(INT_MIN);
ListNode *tail = &dummy;

while (l1 && l2) {
if (l1->val < l2->val) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}

tail->next = l1 ? l1 : l2;
return dummy.next;
}

dummy head(虚链头指针)就是在链表头加一个节点指向head,这样可以避免判断头指针的位置变动,统一处理所有情况,最后返回dummy->next,其实和第一种思路差不多,但更规范。当然上面的代码有个问题就是没有释放dummy head占用的空间。

一般情况下对于一个链表操作的写法框架如下:

1
2
3
4
5
6
7
8
ListNode* ProcessList(ListNode* head){  
ListNode* dummy = new ListNode();
dummy->next = head;
//process the list
head = dummy->next;
delete dummy;//请记得delete
return head;
}

第三种写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* head = NULL, **t = &head;
while(l1 != NULL && l2 != NULL) {
if(l1->val < l2->val) {
*t = l1;
l1 = l1->next;
} else {
*t = l2;
l2 = l2->next;
}
t = &((*t)->next);
}
*t = (l1 != NULL ? l1 : l2);
return head;
}

使用指针的指针(**)来解决这个问题,其实这个类似于第一种写法里面新建一个ListNode p,只不过这里换成了*t,其实这种写法有点绕,个人不是很喜欢。