在這里插入圖片描述

前言
鏈表的實作
- 介面的宣告
- 介面的實作
- 銷毀
- 列印
- 創建結點
- 尾插
- 頭插
- 頭刪
- 尾刪
- 查找
- 指定位置后插入
- 指定位置前插入
- 指定位置后洗掉
- 移除指定位置
力扣題
- 移除鏈表元素:
- 206. 反轉鏈表:
- 876. 鏈表的中間結點:
- 鏈表中倒數第k個結點:
- 21. 合并兩個有序鏈表
- OR36 鏈表的回文結構
- 141. 環形鏈表
- 138. 復制帶隨機指標的鏈表:
- 147. 對鏈表進行插入排序

前言

今天我們的主題是實作單向不帶頭不回圈的單鏈表

鏈表的實作

介面的宣告

typedef int SLTDataTypde;

typedef struct SLTNode 
{
	SLTDataTypde data;
	struct SLTNode *next;
}SLTNode;

//鏈表銷毀
void SLTNodeDestor(SLTNode *ps);
//創建結點
SLTNode *BuySLTNode(int x);
//列印
void SLTprint(SLTNode *ps);
//尾插
void SLTPushBack(SLTNode **ps, int x);
//頭插
void SLTPushFront(SLTNode **ps,int x);
//頭刪
void SLTPopFront(SLTNode **ps);
//尾刪
void SLTPopBack(SLTNode **ps);
//查找
SLTNode* SLTFind(SLTNode *ps, int x);
//指定位置后插入
void SLTInsertAfter(SLTNode *pos, int x);
//指定位置前插入
void SLTInsertBefor(SLTNode **ps, SLTNode *pos, int x);
//移除指定位置之后
void SLTEraseAfter(SLTNode *pos);
//移除指定位置之前
void SLTEraseBefor(SLTNode **ps ,SLTNode *pos);

介面的實作

#include"SLTNode.h"

//創建結點
SLTNode *BuySLTNode(int x) 
{
	SLTNode *tmp = (SLTNode *)malloc(sizeof(SLTNode));
	if (!tmp) 
	{
		perror("BuySLTNode::malloc");
		exit(1);
	}
	tmp->data = x;
	tmp->next = NULL;

	return tmp;
}
//列印
void SLTprint(SLTNode *ps) 
{
	
	SLTNode *cur = ps;
	while (cur != NULL) 
	{
		printf("%d->",cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}	

//鏈表銷毀
void SLTNodeDestor(SLTNode *ps) 
{
	assert(ps);
	while (ps) 
	{
		SLTNode *del = ps;
		ps = ps->next;
		free(ps);
	}
}
//尾插
void SLTPushBack(SLTNode **ps, int x)
{
	SLTNode *newNode = BuySLTNode(x);
	if (*ps == NULL) 
	{
		*ps = newNode;
		
	}
	else 
	{
		SLTNode *tail = *ps;
		//找尾
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newNode;
	}
	

}

//頭插
void SLTPushFront(SLTNode **ps,int x) 
{
	
	SLTNode *newNode = BuySLTNode(x);
	newNode->next = *ps;
	*ps = newNode;
}

//頭刪
void SLTPopFront(SLTNode **ps) 
{
	if (*ps == NULL)
		return;
	SLTNode *delNode = *ps;
	*ps = delNode->next;
	free(delNode);
	delNode = NULL;

}
//尾刪
void SLTPopBack(SLTNode **ps) 
{

	SLTNode *phead = *ps;
	//只有一個結點
	if (phead->next == NULL)
	{
		free(phead);
		*ps = NULL;
		phead = NULL;
	}
	else if (*ps == NULL) 
	{
		return ;
	}
	else
	{	
		SLTNode *cur = *ps;
		SLTNode *prev = NULL;
		//剩多個結點
		while (cur->next != NULL)
		{
			prev = cur;
			cur = cur->next;
		}
		free(cur);
		cur = NULL;
		prev->next = NULL;
	}
	
}

//查找
SLTNode* SLTFind(SLTNode *ps, int x) 
{
	if (ps == NULL)
		return NULL;
	SLTNode *cur = ps;
	while (cur != NULL) 
	{
		if (cur->data == x) 
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

//指定位置后插入
void SLTInsertAfter(SLTNode *pos, int x) 
{
	assert(pos);
	SLTNode *next = pos->next;
	SLTNode *newNode = BuySLTNode(x);
	pos->next = newNode;
	newNode->next = next;
}

//指定位置前插入
void SLTInsertBefor(SLTNode **ps, SLTNode *pos, int x)
{
	assert(pos);
	SLTNode *newNode = BuySLTNode(x);
	if (pos == *ps) 
	{
		newNode->next = *ps;
		*ps = newNode;
	}
	else 
	{
		SLTNode *cur = *ps;
		SLTNode *prev = NULL;

		while (cur != pos) 
		{
			prev = cur;
			cur = cur->next;
		}
		prev->next = newNode;
		newNode->next = cur;
	}
}

//移除指定位置之后
void SLTEraseAfter(SLTNode *pos) 
{
	assert(pos);
	SLTNode *next = pos->next;
	pos->next = next->next;
	free(next);
	next = NULL;
}

//移除指定位置
void SLTEraseBefor(SLTNode ** ps, SLTNode *pos)
{
	assert(pos);
	SLTNode *next = pos->next;
	if (*ps == pos) 
	{
		free(*ps);
		*ps = NULL;
		*ps = next;
	}
	else
	{
		
		SLTNode *prev = NULL;
		SLTNode *cur = *ps;
		while (cur != pos) 
		{
			prev = cur;
			cur = cur->next;
		}
		prev->next = cur->next;
		free(cur);
		cur = NULL;
	}
}

銷毀

//鏈表銷毀
void SLTNodeDestor(SLTNode *ps) 
{
	assert(ps);
	while (ps) 
	{
		SLTNode *del = ps;
		ps = ps->next;
		free(ps);
	}
}

列印

請添加圖片描述

遍歷鏈表的每個結點，列印這個結點的data

//列印
void SLTprint(SLTNode *ps) 
{	
	SLTNode *cur = ps;
	while (cur != NULL) 
	{
		printf("%d->",cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

創建結點

//創建結點
SLTNode *BuySLTNode(int x) 
{
	SLTNode *tmp = (SLTNode *)malloc(sizeof(SLTNode));
	if (!tmp) 
	{
		perror("BuySLTNode::malloc");
		exit(1);
	}
	tmp->data = x;
	tmp->next = NULL;

	return tmp;
}

尾插

請添加圖片描述

創建一個新的結點newNode，找到最后一個結點的位置tail，用tail鏈接newNode，這里要注意的是我們的鏈表的實作是以不帶頭為目的的，所以會是一個空表，如果是空表的情況下，需要將ps初始化成為第一個結點，往后尾插就只需要找尾了，這里要傳二級指標，為了改變外部的指標

//尾插
void SLTPushBack(SLTNode **ps,int x) 
{
	SLTNode *newNode = BuySLTNode(x);
	//如果是空表
	if (*ps == NULL) 
	{
		*ps = newNode;
	}
	else 
	{
		//尾插找尾
		SLTNode *tail = *ps;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newNode;
	}
}

傳遞一級指標無法改變main函式的plist的指標，因為是在不同的堆疊幀中開辟的，只是一份值拷貝，互不影響，所以傳遞二級指標
在這里插入圖片描述

頭插

請添加圖片描述

頭插只需要創建一個新的結點newNode，讓新的結點鏈接ps，再讓ps去做新的頭，由于需要改變外面的指標，還是要傳遞二級指標，頭插即使是面對鏈表為慷訓是不會受影響

//頭插
void SLTPushFront(SLTNode **ps,int x) 
{
	SLTNode *newNode = BuySLTNode(x);
	newNode->next = ps;
	//ps去做新的頭
	*ps = newNode;
}

頭刪

請添加圖片描述

頭刪同樣需要改變外面的指標，所以要傳二級，移除第一個結點，讓第二個結點做新的頭

//頭刪
void SLTPopFront(SLTNode **ps) 
{
	if (*ps == NULL)
		return;
	SLTNode *delNode = *ps;
	*ps = delNode->next;
	free(delNode);
	delNode = NULL;
}

尾刪

請添加圖片描述

尾刪需要考慮三種情況
1、表為空，不需要洗掉，直接回傳
2、只剩一個結點，洗掉這個結點，再置空，也需要改變外面指標的指向，必須傳二級指標
3、有多個結點，定義前驅指標prev，和目標指標cur，當cur指向最后一個結點的時候釋放cur，cur置空，前驅指標prev指向空

//尾刪
void SLTPopBack(SLTNode **ps) 
{

	SLTNode *phead = *ps;
	//只有一個結點
	if (phead->next == NULL)
	{
		free(phead);
		*ps = NULL;
		phead = NULL;
	}
	//表為空直接回傳
	else if (*ps == NULL) 
	{
		return ;
	}
	//剩多個結點
	else 
	{	
		//定義前驅指標和目標指標
		SLTNode *tail= *ps;
		SLTNode *prev = NULL;
		
		while (tail->next != NULL)
		{
			prev = tail;
			tail= tail->next;
		}
		//移除最后一個結點，讓前一個指標指向空
		free(tail);
		cur = NULL;
		prev->next = NULL;
	}
	
}

查找

查找54
請添加圖片描述

找到該結點就回傳，沒找到就回傳空，空表直接回傳

//查找
SLTNode* SLTFind(SLTNode *ps, int x) 
{
	if (ps == NULL)
		return NULL;
	SLTNode *cur = ps;
	while (cur != NULL) 
	{
		if (cur->data == x) 
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

指定位置后插入

在pos后面插入一個新的結點，需要備份pos的下一個結點，先讓newNode指向第二個結點再讓pos指向newNode

//指定位置后插入
void SLTInsertAfter(SLTNode *pos, int x) 
{
	assert(pos);
	SLTNode *next = pos->next;
	SLTNode *newNode = BuySLTNode(x);
	pos->next = newNode;
	newNode->next = next;
}

指定位置前插入

在這里插入圖片描述

1、在指定pos的前面插入，如果pos和ps在同一個位置就是頭插了
2、如果pos出現在鏈表的中間某個位置，要想在pos前插入一個新的結點就必須要找到pos前的一個結點prev，讓這個結點prev指向新的結點newNode，最后讓newNode指向當前結點

//指定位置前插入
void SLTInsertBefor(SLTNode **ps, SLTNode *pos, int x)
{
	assert(pos);
	SLTNode *newNode = BuySLTNode(x);
	if (pos == *ps) 
	{
		newNode->next = *ps;
		*ps = newNode;
	}
	else 
	{
		SLTNode *cur = *ps;
		SLTNode *prev = NULL;

		while (cur != pos) 
		{
			prev = cur;
			cur = cur->next;
		}
		prev->next = newNode;
		newNode->next = cur;
	}
}

指定位置后洗掉

在這里插入圖片描述

next用來保存pos位置的下一個結點，pos指向next的下一個結點，釋放next位置的結點

//移除指定位置之后
void SLTEraseAfter(SLTNode *pos) 
{
	//表為空不做處理
	if(pos == NULL)
	{
		return ;
	}
	assert(pos);
	SLTNode *next = pos->next;
	pos->next = next->next;
	free(next);
	next = NULL;
}

移除指定位置

prev和cur一起一后，當cur與pos相遇了，就將prev鏈接cur的下一個結點，釋放pos位置的結點，將指標置空

在這里插入圖片描述

如果plist和pos指向一起，就是頭刪操作了

在這里插入圖片描述

//移除指定位置
void SLTEraseBefor(SLTNode ** ps, SLTNode *pos)
{
	assert(pos);
	SLTNode *next = pos->next;
	//pos等于ps，頭刪
	if (*ps == pos) 
	{
		free(*ps);
		*ps = NULL;
		*ps = next;
	}
	else
	{
		SLTNode *prev = NULL;
		SLTNode *cur = *ps;
		while (cur != pos) 
		{
			prev = cur;
			cur = cur->next;
		}
		prev->next = cur->next;
		free(cur);
		cur = NULL;
	}
}

力扣題

移除鏈表元素:

點我.
在這里插入圖片描述
考慮兩種場景

1、如果表的第一個結點的值就是val，那么就是頭刪了，釋放第一個結點，需要將head的指向改變，指向下一個結點
2、如果表的所有結點全是val的情況，head的指向就可以一直改變，直到指向NULL，最后回傳去的就是NULL

鏈表移除結點的變形題，把特殊場景處理就能搞定

struct ListNode* removeElements(struct ListNode* head, int val){
  
    struct ListNode *prev = NULL;
    struct ListNode *cur = head;
    while(cur != NULL)
    {
    	//值為val
        struct ListNode *del = NULL;
        if(cur->val != val)
        {
            prev = cur;
            cur = cur->next;
        }
        //值不為val
        else
        {
            //如果cur是頭的情況
            struct ListNode *next = cur->next;
            if(prev == NULL)
            {
                free(cur);
                head = next;
                cur = next;
            }
            //cur不是頭
            else
            {
                prev->next = next;
                free(cur);
                cur = next;
            }
        }
    }
    return head;
}

第二種寫法：帶哨兵位的頭節點，可以讓prev指向哨兵位結點，這樣就不需要考慮prev是否會存在空指標的問題了，同樣的prev和cur一起一后，找到了值位val的結點，就釋放該節點，cur繼續指向下一個位置，最后只需要回傳哨兵位結點的下一個位置

struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode* guard = (struct ListNode*)malloc(sizeof(struct ListNode));
    guard->next = head;

    struct ListNode *prev = guard;
    struct ListNode *cur = head;
    while(cur != NULL)
    {
        if(cur->val != val)
        {
            prev = cur;
            cur = cur->next;
        }
        else
        {
            
            struct ListNode *next = cur->next;
           
            prev->next = next;
            free(cur);
            cur = next;
        }
    }
    return guard->next;
}

在這里插入圖片描述

206. 反轉鏈表:

點我.
實作思路

使用三個指標迭代的方法，prev和cur用來逆置結點的指向，next保證cur能找到下一個結點的位置，直到cur指向空了，回圈停止，回傳prev指標，整個鏈表也就逆置了

struct ListNode* reverseList(struct ListNode* head){
    if(head == NULL)
    {
        return NULL;
    }
    
    struct ListNode* cur = head;
    struct ListNode* prev = NULL;
    struct ListNode* next = cur->next;

    while(cur)
    {
       //逆置
       cur->next = prev;
       //迭代
       prev = cur;
       cur = next;
       if(next != NULL)
       next = next->next;
    }

    return prev;
}

思路二：必做，鏈表頭插的變型題，將原鏈表遍歷一遍，取原鏈表的結點頭插到新的表中

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode *newhead = NULL;
  
    struct ListNode *cur = head;
    while(cur)
    {
        struct ListNode *next = cur->next;
        //頭插
        cur->next = newhead;
        newhead = cur;
        //迭代
        cur = next;
    }
    return newhead;
}

876. 鏈表的中間結點:

點我.
在這里插入圖片描述

快慢指標解法，快指標走兩步慢指標走一步，當快指標走到鏈表NULL位置的時候，或者快指標走到最后一個結點的位置，回圈終止，回傳慢指標

struct ListNode* middleNode(struct ListNode* head){
    if(head == NULL)
    {
        return NULL;
    }
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while(fast && fast->next)
    {
        slow = slow->next;
       
        fast = fast->next->next;
       
    }

    return slow;
}

鏈表中倒數第k個結點:

點我.
在這里插入圖片描述

快指標先走k步，快指標走完k步后，快指標和慢指標一起走，當快指標走完了，slow就是倒數第k個結點，就回傳slow的位置

極端情況：如果fast先走k步，k大于鏈表的長度，鏈表可能存在空表，是空表就回傳NULL

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    // write code here
    struct ListNode* fast = pListHead;
    struct ListNode* slow = pListHead;
    
    while(k--)
    {
        //k大于鏈表長度，fast已經走到NULL了，
        if(fast == NULL)
            return NULL;
        fast = fast->next;
    }
    
    while(fast)
    {
       fast = fast->next;
       slow = slow->next;
    }
    return slow;
}

21. 合并兩個有序鏈表

鏈接: 點我.
在這里插入圖片描述

思路：合并兩個鏈表只需要將原鏈表中最小的值尾插到新鏈表中去

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    if(l1 == NULL)
    return l2;
    if(l2 == NULL)
    return l1;
    if(l1 == NULL && l2 == NULL)
    return NULL;
    
    struct ListNode* newList = NULL;
    struct ListNode *tail = newList;
	//取下最小值做新鏈表的頭
    if(l1->val < l2->val)
    {
        newList = tail = l1;
        l1 = l1->next;
    }
    else
    {
        newList = tail = l2;
        l2 = l2->next;
    }
	//取兩個鏈表中最小值尾插到新的鏈表中去
    while(l1 && l2)
    {
       if(l1->val < l2->val)
       {
           tail->next = l1;
           l1 = l1->next;
       }
       else
       {
           tail->next = l2;
           l2 = l2->next;
       }
       tail = tail->next;
    }

	//如果有一個鏈表還沒遍歷完就繼續尾插到新鏈表去
    if(l1)
    {
        tail->next = l1;
    }
    if(l2)
    {
        tail->next = l2;
    }

    return newList;
}

帶哨兵位的頭節點不需要考慮新鏈表頭尾都是是NULL的這種情況

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
	//創建哨兵頭節點
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* tail = head;
    tail->next = NULL;

    while(l1 && l2)
    {
        if(l1->val < l2->val)
        {
            tail->next = l1;
            l1 = l1->next;
        }
        else
        {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }

    //還剩的
    if(l1){
        tail->next = l1;
    }
    if(l2){
        tail->next = l2;
    }
	
	//釋放動態開辟的結點，回傳新的頭
    struct ListNode* node = head;
    head = head->next;
    free(node);
    return head;
}

OR36 鏈表的回文結構

鏈接: 點我 .
在這里插入圖片描述

解題思路：先找出中間結點（快慢指標法），將中間結點起始位置往后整體逆置，回傳逆置后的頭指標，得到后部分逆置的鏈表，再跟原鏈比較

class PalindromeList {
public:
    struct ListNode* middleNode(struct ListNode* head){
    if(head == NULL)
    {
        return NULL;
    }
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while(fast && fast->next)
    {
        slow = slow->next;
       
        fast = fast->next->next;
       
    }

    return slow;
}
    struct ListNode* reverseList(struct ListNode* head){
    if(head == NULL)
    {
        return NULL;
    }
    
    struct ListNode* cur = head;
    struct ListNode* prev = NULL;
    struct ListNode* next = cur->next;

    while(cur)
    {
       //逆置
       cur->next = prev;
       //迭代
       prev = cur;
       cur = next;
       if(next != NULL)
       next = next->next;
    }

    return prev;
}
    bool chkPalindrome(ListNode* A) {
        // write code here
        //找到中間結點整體逆置，最后比較
        struct ListNode* mid = middleNode(A);
        struct ListNode* rhead = reverseList(mid);
        
        //比較
        while(A && rhead)
        {
            if(A->val != rhead->val)
            {
                return false;
            }
            else
            {
                A = A->next;
                rhead = rhead->next;
            }
        }
        return true;
    }
};

在這里插入圖片描述
160. 相交鏈表
鏈接: 點我.

鏈表的相交并不是直線的相交，而是兩個鏈表中存在一個公共結點，這樣的鏈表我們可以稱它是相交鏈表，比較結點的地址，如果相同那么就是相交的，否則不是，讓長距離的先走差距步，最后再同時走，如果中間相交就回傳該結點，否則回傳NULL

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    //記錄鏈表的長度
    int lenA = 0,lenB = 0;
    struct ListNode *curA = headA;
    struct ListNode *curB = headB;
    while(curA->next)
    {
        lenA++;
        curA = curA->next;
    }
    while(curB->next)
    {
        lenB++;
        curB = curB->next;
    }
    //如果不相遇那么鏈表的最后一個結點一定不同
    if(curA != curB)
    return NULL;
    //定義長的鏈表，定義短的鏈表
    struct ListNode * longlist = headA, *shortlist = headB;
    int gap = abs(lenB - lenA);
    if(lenA < lenB)
    {
        longlist = headB;
        shortlist = headA;
    }
    //長鏈表先走gap步
    while(gap--)
    {
        longlist = longlist->next;
    }
    //最后一起走
    while(longlist != shortlist)
    {
        longlist = longlist->next;
        shortlist = shortlist->next;
    }

    return longlist;
}

141. 環形鏈表

鏈接: 點我.
在這里插入圖片描述

快慢指標解法，快指標走兩步，慢指標走一步，當他們相遇了，就能證明鏈表是環形鏈表，如果fast走到NULL的位置或者fast的下一個結點是空了，那么鏈表就不為環形

bool hasCycle(struct ListNode *head) {
    struct ListNode * fast = head;
    struct ListNode * slow = head;
    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow)
        {
            return true;
        }
    }
    return false;
}

延申問題

1、為什么slow走一步，fast走兩步，它們一定會在環里面相遇，會不會永遠追不上，請證明
2、slow走一步，fast走3步？走4步？走n步行不行？請證明！
3、求環的入口點

在這里插入圖片描述
不會，假設slow進環的時候fast跟slow的差距是N，緊接著追擊的程序，fast往前走2步，slow走1步，它們每次一走，它們之間的距離縮小1，N-1 N-2 … 2 1 0，直到等于0的時候就相遇了

2、slow走一步，fast走3步？走4步？走n步行不行？請證明！
假設slow進環的時候fast跟slow的差距是N，緊接著追擊的程序，fast往前走3步，slow走1步，它們每次一走，它們之間的距離縮小2，會分兩種情況，如果是奇數個，如果是偶數個呢？如果是偶數個可以相遇，如果是奇數（-1）個并不會相遇，假設環的大小是C，那么slow和falst的差距就是C-1了，如果C-1恰好是奇數就永遠追不上
在這里插入圖片描述
總結：如果slow進環時，slow跟fast的差距是奇數，且環的長度是偶數，那么它們兩個再環里面就會一直打圈

解題思路：
將fast和slow的相遇點找出來，meet表示相遇點，從相遇點meet開始
head走一步meet走一步，如果他們相遇了，那么這就是入口點

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode * fast = head;
    struct ListNode * slow = head;
    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        //相遇
        if(fast == slow)
        {
             //相遇后,meet從相遇點開始走，head從起點開始走，
            struct ListNode *meet = fast;
            while(head != meet)
            {
                head = head->next;
                meet = meet->next;
            }
            //當head和meet相遇了，這就是入口點
            if(meet == head)
            {
                return meet;
            }
        }   
    }

    return NULL;
}

138. 復制帶隨機指標的鏈表:

點我.
在這里插入圖片描述

解題思路：
要想復制一份鏈表比較得保證新鏈表的結點關系和原鏈表保持一致，并且新鏈表的每個結點的值以及結點中兩個指標的指向都必須與原鏈表結點一樣，將拷貝鏈表的結構構建出來后，同步拷貝鏈表和原鏈表兩個指標的指向，最后將拷貝鏈表拆解下來，同時還原原鏈表結點的鏈接的關系，最后回傳拷貝鏈表的頭

在這里插入圖片描述

struct Node* copyRandomList(struct Node* head) {
    if(head == NULL)
    {
        return NULL;
    }
    struct Node* cur = head;
    //建立拷貝結點的關系
	while(cur)
    {
       struct Node* next = cur->next;
       struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
       copy->val = cur->val;
       copy->next = next;
       cur->next = copy;
       cur = next;
    }
    //同步拷貝結點的隨機指標
    cur = head;
    while(cur)
    {
        struct Node* copy = cur->next;
        struct Node* next = copy->next;
        if(cur->random == NULL)
        {   
            copy->random = NULL; 
        }
        else
        {
            copy->random = cur->random->next;
        }
        cur = next;
    }
    //創建哨兵位頭節點，新鏈表的尾結點
    cur = head;
    struct Node* copyhead,*copytail;
    copyhead = copytail = (struct Node*)malloc(sizeof(struct Node));
    while(cur)
    {
        //復原新鏈表的關系
        struct Node* copy = cur->next;
        struct Node* next = copy->next;

        copytail->next = copy;
        copytail = copytail->next;
        cur->next = next;

        cur = next;
    }
    //釋放頭結點
    struct Node* guard = copyhead;
    copyhead = copyhead->next;
    free(guard);
    return copyhead;
}

147. 對鏈表進行插入排序

鏈接: 點我.
在這里插入圖片描述

解題思路：
取下原鏈表中的第一個結點將他當成一個有序的新鏈表看待，再比較剩余結點構成的鏈表，比較完后將舊鏈表中剩余的結點按照順序方式插入到新的鏈表中

struct ListNode* insertionSortList(struct ListNode* head){
    if(head == NULL || head->next == NULL)
    {
        return head;
    }
    struct ListNode* cur = head->next;
    struct ListNode* rhead = head;
    rhead->next = NULL;
    while(cur)
    {
        struct ListNode* p = NULL;
        struct ListNode* c = rhead;
        struct ListNode* next = cur->next;
       
        while(c)
        {
           if(cur->val < c->val)
           {
               break;
           }
           else
           {
               p = c;
               c = c->next;
           }
        }
        //頭插
        if(p == NULL)
        {
            cur->next = c;
            rhead = cur;
          
        }
        //順序位置處插入
        else
        {
            p->next = cur;
            cur->next = c;
        }
        cur = next;
    }
    return rhead;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/307357.html

標籤：其他

上一篇：PCI、PCIe、Mini PCIe、SATA、mSATA、M.2

下一篇：??強烈推薦！Word、Excel、PPT、PDF在線預覽解決方案

單鏈表C語言實作附加力扣題

目錄

前言

鏈表的實作

介面的宣告

介面的實作

銷毀

列印

創建結點

尾插

頭插

頭刪

尾刪

查找

指定位置后插入

指定位置前插入

指定位置后洗掉

移除指定位置

力扣題

移除鏈表元素:

206. 反轉鏈表:

876. 鏈表的中間結點:

鏈表中倒數第k個結點:

21. 合并兩個有序鏈表

OR36 鏈表的回文結構

141. 環形鏈表

138. 復制帶隨機指標的鏈表:

147. 對鏈表進行插入排序