合并兩個有序鏈表

link.

將兩個升序鏈表合并為一個新的 升序 鏈表并回傳，新鏈表是通過拼接給定的兩個鏈表的所有節點組成的，

示例 1：

輸入：l1 = [1,2,4], l2 = [1,3,4] 輸出：[1,1,2,3,4,4]

示例 2：

輸入：l1 = [], l2 = [] 輸出：[]

示例 3：

輸入：l1 = [], l2 = [0] 輸出：[0]

提示：

兩個鏈表的節點數目范圍是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非遞減順序 排列

思路，我們可以取節點下來尾插，取兩節點中的較小的值尾插在新節點里面，我們同時可以弄一個哨兵位的頭節點，尾插的時候，我們還可以定義一個尾指標，指向鏈表的尾部

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    if(list1==NULL)//如果list1為空的話，就回傳list2，無論list2是否為空都是符合的
    {
return list2;
    }
    if(list2==NULL)//同理
    {
        return list1;
    }
struct ListNode*head=NULL;//一開始初始化新頭和尾都是NULL
struct ListNode*tail=NULL,*n1=list1,*n2=list2;
//1.沒有帶哨兵位的頭節點
/*if(n1->val<=n2->val)
{
    head=tail=n1;
    n1=n1->next;
}
//這就是把里面判斷頭為空給跳過去了
else
{
    head=tail=n2;
    n2=n2->next;
}*/
//帶哨兵位的頭
//head=tail=(struct ListNode*)malloc(sizeof(struct ListNode));//回傳的時候是head->next;再free掉 
while(n1&&n2)
{
    if(n1->val<=n2->val)
    {
        if(head==NULL)//如果新鏈表沒有節點，就把第一個節點頭和尾都為n1
        {
            head=tail=n1;
          
        }
        else
        {
            tail->next=n1;//tail指向n1部分
            tail=n1;//再把tail更新一下
         
        }
          n1=n1->next;
    }
       else//同理
    {
        if(head==NULL)
        {
            head=tail=n2;
        
        }
        else
        {
            tail->next=n2;
            tail=n2;
           
        }
         n2=n2->next;
    }
}
if(n1)//如果n1不為空，那么就把n1整個鏈接到tail的后面
{
tail->next=n1;
}
else
{
    tail->next=n2;
}
return head;//回傳頭
}

移除鏈表元素

link.

給你一個鏈表的頭節點 head 和一個整數 val ，請你洗掉鏈表中所有滿足 Node.val == val 的節點，并回傳 新的頭節點 ，

示例 1：

輸入：head = [1,2,6,3,4,5,6], val = 6 輸出：[1,2,3,4,5]

示例 2：

輸入：head = [], val = 1 輸出：[]

示例 3：

輸入：head = [7,7,7,7], val = 7 輸出：[]

提示：

串列中的節點數目在范圍 [0, 104] 內
1 <= Node.val <= 50
0 <= val <= 50

思路

弄一個新鏈表，如果不為val就把原鏈表的節點鏈接到新鏈表里面去
為val就跳過去

struct ListNode* removeElements(struct ListNode* head, int val){
if(head==NULL)
{
    return NULL;
}
//新定義一個頭節點，尾節點
struct ListNode*newhead=NULL,*tail=NULL,*cur=head;
while(cur!=NULL)
{
    if(cur->val!=val)//不為val
    {
        if(newhead==NULL)
        {
            newhead=tail=cur;
        }
        else
        {
            tail->next=cur;
            tail=cur;
        }
     
        cur=cur->next;
    }
    else//為val
    {
            cur=cur->next;  
              
    }
}
//[7,6,7,7]   val=7
//新鏈表是[6,7,7],后面也會一起鏈接進去，所以我們要處理后面的val，而且后面全是val，prev指向l的下一個
struct ListNode*l=newhead;
struct ListNode*prev=NULL;//prev是l的前驅
while(l)
{
if(l->val!=val)
{
    prev=l;
    l=l->next;
}
else
{
    prev->next=l->next;//prev指向后一個，跳過那個點
free(l);//釋放掉
    l=prev->next;l跳到prev的后一個，這個時候prev的后一個已經被改變了
}  

}
return newhead;
}

分割鏈表

link.

給你一個鏈表的頭節點 head 和一個特定值 x ，請你對鏈表進行分隔，使得所有 小于 x 的節點都出現在 大于或等于 x 的節點之前，你不需要 保留 每個磁區中各節點的初始相對位置

示例 1：

輸入：head = [1,4,3,2,5,2], x = 3 輸出：[1,2,2,4,3,5]

示例 2：

輸入：head = [2,1], x = 2 輸出：[1,2]

提示：

鏈表中節點的數目在范圍 [0, 200] 內
-100 <= Node.val <= 100
-200 <= x <= 200

思路

我們可以弄兩個鏈表，一個鏈表是小于x的鏈表，一個是大于等于x的鏈表
后面把兩個鏈表鏈接起來，回圈后面都指向NULL，把后面都截斷掉，避免還有鏈接

struct ListNode* partition(struct ListNode* head, int x){
struct ListNode*lesshead=NULL,*lesstail=NULL,*morehead=NULL,*moretail=NULL,*cur=head;
lesshead=lesstail=(struct ListNode*)malloc(sizeof(struct ListNode));
//
morehead=moretail=(struct ListNode*)malloc(sizeof(struct ListNode));
while(cur)
{
    if(cur->val<x)//小于x的鏈接起來
    {
        lesstail->next=cur;
        lesstail=cur;
        cur=cur->next;
    }
    else//大于x的鏈接起來
    {
        moretail->next=cur;
        moretail=cur;
        cur=cur->next;
    }
}
lesstail->next=NULL;//吧tail后面都置成空哦
moretail->next=NULL;
lesstail->next=morehead->next;//再連接起來
struct ListNode*new=lesshead->next;
free(morehead);
free(lesshead);
morehead=lesshead=NULL;
return new;


}