---

---

一、JZ76 删除链表中重复的结点

描述
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表 1->2->3->3->4->4->5 处理后为 1->2->5
数据范围：链表长度满足 0 \le n \le 1000 \0≤n≤1000 ，链表中的值满足 1 \le val \le 1000 \1≤val≤1000
进阶：空间复杂度 O(n) ，时间复杂度 O(n)

示例1
输入：
{1,2,3,3,4,4,5}
返回值：
{1,2,5}
示例2
输入：
{1,1,1,8}
返回值：
{8}

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pHead ListNode类 
 * @return ListNode类
 */
struct ListNode* deleteDuplication(struct ListNode* pHead ) {
    if(pHead==NULL||pHead->next==NULL)
    {
        return pHead;
    }
    struct ListNode*cur=pHead;
    struct ListNode*prev=NULL;
    struct ListNode*next=cur->next;
    while(next)
    {
        if(cur->val!=next->val)
        {
            prev=cur;
            cur=next;
            next=next->next;
        }
        else
        {
            while(next->val==cur->val&&next!=NULL)
            {
                next=next->next;
            }
              cur=next;
            if(prev!=NULL)
            {
                prev->next=next;
            }
            else
            {
                pHead=next;
            }
            if(next!=NULL)
            {
                next=next->next;
            }
        }
    }
    return pHead;
}
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
52
53
54

本题需要考虑三种情况:
1.中间删除：

例：1 2 3 3 4 4 5

2.头删:
由于刚开始next值为NULL,所以直接将next赋给pHead
例：1 1 1 3 4

3.尾删:
next在循环中会一直走到NULL 所以要加上遍历条件

如果next为NULL ,NULL->next则会报错

例:2 3 4 5 5 5

二、147. 对链表进行插入排序

给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。
插入排序 算法的步骤:
插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。
下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。
对链表进行插入排序。

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


struct ListNode* insertionSortList(struct ListNode* head){
    if(head==NULL||head->next==NULL)//当为1个节点或2个节点
    {
        return head;
    }
        struct ListNode*sorthead=head;
        struct ListNode*cur=head->next;
        sorthead->next=NULL;
        while(cur!=NULL)
        {
            struct ListNode*next=cur->next;
            if(cur->val<sorthead->val)//如果值比头节点小 就头插
            {
                cur->next=sorthead;
                sorthead=cur;
            }
            else// 比头节点大 就中间插 /尾插
            {
                struct ListNode*sortprev=sorthead;
                struct ListNode*sortcur=sorthead->next;
                while(sortcur!=NULL)
                {
                    if(cur->val<=sortcur->val)//当在中间找到合适的插入点
                    {
                        sortprev->next=cur;
                        cur->next=sortcur;
                        break;//找到后就跳出循环
                    }
                    else
                    {
                        sortprev=sortcur;
                        sortcur=sortcur->next;
                    }
                }
                if(sortcur==NULL)//如果走到尾 说明要尾插
                {
                   sortprev->next=cur;
                   cur->next=NULL;
                }
            }
            cur=next;
        }
        return sorthead;
}
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
52
53

本题主要思想是， 将第一个节点单独拿出来，如果cur的值比它小，则进行头插，如果cur值比它大，
则进行 中间插或者尾插
例：

1.
因为2的值比sorthead小 所以头插
2.
1比2还小 ，所以再次头插

三、138. 复制带随机指针的链表

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */

struct Node* copyRandomList(struct Node* head) {
	struct Node*cur=head;
    if(head==NULL)
    {
        return NULL;
    }
    while(cur!=NULL)//1.拷贝节点到节点后面
    {
        struct Node*copy=(struct Node*)malloc(sizeof(struct Node));
        copy->next=NULL;
        copy->random=NULL;
        copy->val=cur->val;
        struct Node*next=cur->next;
        cur->next=copy;
        copy->next=next;
        cur=next;
    }
    cur=head;
    while(cur!=NULL)//2.原节点的random后一个是拷贝节点的random
    {
      struct Node*copy=cur->next;
      if(cur->random!=NULL)
      {
          copy->random=cur->random->next;
      }
      else
      {
          copy->random=NULL;
      }
      cur=copy->next;
    }
    cur=head;
    struct Node* copyhead=cur->next;
    while(cur!=NULL)//3.断开与拷贝节点连接 
    {
        struct Node*copy=cur->next;
        struct Node*next=copy->next;
        cur->next=next;
        if(next!=NULL)
        {
         copy->next=next->next;
        }
        else
        {
            copy->next=NULL;
        }
        cur=next;
    }
    return copyhead;
}
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
52
53
54
55
56
57
58
59

本题主要思想为 1.拷贝出节点 并连接到原节点的后面 。2.通过原节点的random找到拷贝节点的random 。
3.断开原节点与拷贝节点的联系 并返回拷贝节点
例：