21. Merge Two Sorted Lists

合并两个有序链表

解题思路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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
	//定义两个指针指向两个链表
	struct ListNode *p=(struct ListNode *)malloc(sizeof(struct ListNode));
	struct ListNode *head=p,*p1=list1,*p2=list2;
    
  //输入检查
  if(!p1 && !p2) return p1;
	else if(!p1) return p2;
	else if(!p2) return p1;

	//分别比较放入新链表p
	while(p1&&p2){
		if(p1->val > p2->val){
			p->next = p2;
			p2 = p2->next;
		}
		else if(p2->val > p1->val){
			p->next = p1;
			p1 = p1->next;
		}
		else if(p1->val == p2->val){
			p->next = p1;
			p1 = p1->next;
			p = p->next;
			p->next = p2;
			p2 = p2->next;
		}
		p = p->next;
	}

  //将剩余节点放入p尾部
	if(p1) p->next = p1;
	if(p2) p->next = p2;

  //释放头结点并返回头指针
	p = head;
	head = head->next;
	free(p);
	return head;
}

解题思路2

用递归分别返回较小节点依次向后遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
  
  //判空
	if(!list1) return list2;
	if(!list2) return list1;
  
  //比较较小节点并返回
	if(list1->val <= list2->val){
		list1->next = mergeTwoLists(list1->next,list2);
		return list1;
	}
	if(list2->val <= list1->val){
		list2->next = mergeTwoLists(list1,list2->next);
		return list2;
	}
    return list1;
}

86. Partition List

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* partition(struct ListNode* head, int x){
    
  //判空
	if(!head) return head;
  if(!head->next) return head;

	//新建两个链表
	typedef struct ListNode node;
	node *p=head;
	node *p1head=(node *)malloc(sizeof(node));
	node *p2head=(node *)malloc(sizeof(node));
	node *p1=p1head;
	node *p2=p2head;
	p1->next = NULL;
	p2->next = NULL;

  //按大小分别插入两个链表
	while(p){
		if(p->val >= x){
			p2->next = p;
			p2 = p2->next;
		}
		else{
			p1->next = p;
			p1 = p1->next;
		}
			p = p->next;
	}

  //去头输出
	p1->next = p2head->next;
	p2->next = NULL;
	return p1head->next;
}