Merge Lists

发表于 | 分类于

Merge Lists

题目描述1：

给定两个有序链表的头节点，要求返回将这两个链表合并后的头结点。

例子：

具体描述看LeetCode21

解题思路：

代码如下：

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;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* head1 = l1;
        ListNode* head2 = l2;
        if(head1 == NULL || head2 == NULL)
            return head1 == NULL ? head2 : head1;
        // 只要一个为空就返回非空的那个链表
        ListNode* head = head1->val <= head2->val ? head1 : head2;
        //定义头结点中较小的那个为头
        ListNode* cur1 = head == head1 ? head1 : head2;
        ListNode* cur2 = head == head1 ? head2 : head1;
        //定义遍历的两个链表头节点，其中cur1代表较小的那个
        ListNode* pre = NULL;
        ListNode* next = NULL;
        while(cur1 != NULL && cur2 != NULL){
            if (cur1->val <= cur2->val){
                pre = cur1;
                cur1 = cur1->next;
            }
            else{
                next = cur2->next;
                pre->next = cur2;
                cur2->next = cur1;
                pre = cur2;
                cur2 = next;
                //重新连接链表
            }
        }
        pre->next = cur1 == NULL ? cur2 : cur1;
        //pre的下一个节点连接到非空的那个剩余链表上
        return head;
    }
};