合并两个升序链表，哨兵位的理解

开始时也要判断是否有一个链表本来就是空，如果是，直接返回另外一个链表

代码：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    if(list1==NULL)
    {
        return list2;
    }

     if(list2==NULL)
    {
        return list1;
    }
struct ListNode* cur1=list1;
struct ListNode* cur2=list2;
struct ListNode* newnode=NULL;
struct ListNode* tail=NULL;
while(cur1&&cur2)
{
    if(cur1->val<=cur2->val)
    {
        if(tail==NULL)
        {
            newnode=tail=cur1;
        }else
        {
            tail->next=cur1;
            tail=tail->next;
        }
        cur1=cur1->next;
    }else
    {
         if(tail==NULL)
        {
            newnode=tail=cur2;
        }else
        {
            tail->next=cur2;
            tail=tail->next;

        }
        cur2=cur2->next;
    }
}
if(cur1)
{
    tail->next=cur1;
}
if(cur2)
{
    tail->next=cur2;
}
return newnode;
}
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

上述代码因为如果拿下的数是第一个节点，那么就要头插。这样就不得不判断

这样显得反锁了一点，那么我们是否有一种方法，使得不管是不是头插，都可以只用

这一个代码就实现呢，那么我们就引进了带哨兵位的链表

所以对于此题，我们还可以用哨兵位的方法来做：

代码：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    if(list1==NULL)
    {
        return list2;
    }

     if(list2==NULL)
    {
        return list1;
    }
struct ListNode* cur1=list1;
struct ListNode* cur2=list2;
struct ListNode* newnode=NULL;
struct ListNode* tail=NULL;
newnode=tail=(struct ListNode* )malloc(sizeof(struct ListNode));
while(cur1&&cur2)
{
    if(cur1->val<=cur2->val)
    {
        
            tail->next=cur1;
            tail=tail->next;
        
        cur1=cur1->next;
    }else
    {
          tail->next=cur2;
            tail=tail->next;

        
        cur2=cur2->next;
    }
}
if(cur1)
{
    tail->next=cur1;
}
if(cur2)
{
    tail->next=cur2;
}
struct ListNode* per=newnode;
newnode=newnode->next;
free(per);
return newnode;
}
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