黑客灵魂

这个屌丝很懒，什么也没留下！

热门标签

【数据结构】链表-C语言版_顺序表链表的应用错误及原因

作者：黑客灵魂 | 2024-07-10 16:59:58

踩

顺序表链表的应用错误及原因

顺序表缺点

顺序表随机访问很方便，但是也会有不足啊：

（1）挪动数据时间开销较大：头部/中间的插入删除，需要挪动后面的所有数据，时间复杂度为O(N)

（2）增容有代价：增容需要重新申请空间，拷贝数据，释放旧空间，系统消耗不小

（3）空间浪费：增容一般增至原来的2倍大空间，会有空间浪费，假如当前容量为100，满了以后增容到200，再继续插入了5个数据，后面没有插入数据了，这就浪费了95个空间。

不存在扩容代价、不存在空间浪费、按需申请空间、头部或者中间插入数据而不需要挪动数据的链表可以解决以上问题。

链表的概念和结构

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

注意：

（1）链式结构在逻辑上连续，逻辑上不一定连续。（逻辑结构是想象的，物理结构是内存中实际存储的）。

（2）结点一般从堆上申请。

（3）堆上申请的空间时按照一定策略分配的，两次申请的空间可能连续也可能不连续。

链表的分类

有8种链表结构：

（1）单向和双向

（2）带头单链表和不带头单链表

（3）非循环链表和循环链表

以上3种分类的链表一共有2*2*2=8种组合，最实用的有两种：

（1）无头单向非循环链表：结构简单，一般不会用来单独存储数据。十几种更多是作为其他数据结构的子结构，如哈希桶，图的邻接表等。

（2）带头双向循环链表：结构最复杂，一般用来单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。虽然结构复杂，但是使用代码实现以后会发现该结构会带来很多优势，实现反而简单。

链表的实现

如果需要交换两个int的值，那么swap函数的实参是两个int的地址，形参是两个int型指针。


#define  _CRT_SECURE_NO_WARNINGS  1
#include<stdio.h>
 
void swap(int* pa, int* pb)//用两个指针作为形参接收两个地址
{
	int temp = *pa;
	*pa = *pb;
	*pb = temp;
}
 
int main()
{
	int a = 3;
	int b = 5;
	swap(&a, &b);//实参是两个int的地址
	printf("a = %d\n", a);
	printf("a = %d\n", b);
	return 0;
}

同理，对于链表的增删，如果需要改变指针指向，就要传指针的地址，即二级指针。

链表实现：

025-SList.h 链表函数定义


#define  _CRT_SECURE_NO_WARNINGS  1
#pragma once
 
typedef int SLTDataType;
 
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;
 
//单向+不带头+非循环
 
//打印
void SListPrint(SLTNode* plist);
 
//尾插(需要改变指针指向，就要传指针的地址，即二级指针，如需要交换两个int的值，那么swap函数的实参是两个int的地址，形参是两个int型指针)
void SListPushBack(SLTNode** plist,SLTDataType x);
 
//头插
void SListPushFront(SLTNode** plist, SLTDataType x);
 
//尾删
void SListPopBack(SLTNode** plist);
 
//头删
void SListPopFront(SLTNode** plist);
 
//单链表查找
SLTNode* SListFind(SLTNode* plist, SLTDataType x);
 
//在pos之后插入x
void SListInsertAfter(SLTNode* pos, SLTDataType x);
 
//在pos之前插入x
void SListInsertBefore(SLTNode** plist,SLTNode* pos, SLTDataType x);
 
//在pos之前插入x，没有头的情况:后插一个值为x的节点，再跟前面的结点值交换。
void SListInsertBeforeNoHead(SLTNode* pos, SLTDataType x);
 
//删除后一个节点
void SListEraseAfter(SLTNode* pos);
 
//删除当前位置
void SListEraseCur(SLTNode** plist, SLTNode* pos);

025-SList.c 链表函数实现


#define  _CRT_SECURE_NO_WARNINGS  1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
 
#include "025-SList.h"
 
//打印
void SListPrint(SLTNode* plist)
{
	SLTNode* cur = plist;
 
	//找空节点，找到后不再打印
	while (cur != NULL)
	{
		printf("%d->", cur->data);
 
		//让cur指向下一个节点
		cur = cur->next;
	}
 
	printf("NULL\n");
}
 
//创建新节点
SLTNode* BuySLTNode(SLTDataType x)
{
	//申请空间
	SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
	if (node == NULL)
	{
		return NULL;
	}
 
	//数据赋值
	node->data = x;
 
	//指针赋值
	node->next = NULL;
 
	return node;
}

（1）尾插：


//尾插
void SListPushBack(SLTNode** pplist, SLTDataType x)
{
	SLTNode* newNode = BuySLTNode(x);
 
	//不能使用tail->next != NULL直接作为判断条件，因为有可能是空链表，对空指针解引用会造成非法访问，因此要分两种情况
 
	if (*pplist == NULL)//链表为空
	{
		*pplist = newNode;
	}
	else //链表不为空
	{
		SLTNode* tail = *pplist;
 
		//找尾节点
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newNode;
	}
}

（2）头插，不需要区分空链表和非空链表


//头插
void SListPushFront(SLTNode** pplist, SLTDataType x)
{
	SLTNode* newNode = BuySLTNode(x);
	newNode->next = *pplist;//新节点的下一个指向第一个节点
	*pplist = newNode;//链表指向新节点
}

（3）尾删


//尾删
void SListPopBack(SLTNode** pplist)
{
	//链表为空
	if (*pplist == NULL)
	{
		return;
	}
	//链表只有一个结点
	else if ((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	//链表有多个结点
	else
	{
		SLTNode* pre = NULL;//后面用该结点指向尾节点的前驱结点，因为删除为节点后，尾节点的前驱结点的后继结点要赋为空指针
		SLTNode* tail = *pplist;
 
		//寻找最后一个结点，循环结束后，tail为尾结点，pre为尾结点的前驱结点
		while (tail->next != NULL)
		{
			pre = tail;
			tail = tail->next;
		}
 
 
		free(tail);
		tail = NULL;
 
		pre->next = NULL;
	}
}

（4）头删


//头删
void SListPopFront(SLTNode** pplist)
{
	if (*pplist == NULL)
	{
		return;
	}
	else
	{
		SLTNode* next = (*pplist)->next;//保存后一个节点
		free(*pplist);
		*pplist = next;//链表指向下一个节点
	}
}

（5）单链表查找


//单链表查找
SLTNode* SListFind(SLTNode* plist, SLTDataType x)
{
	SLTNode* cur = plist;
	while (cur)//没找到就往后继续走
	{
		if (cur->data == x)
		{
			return cur;//找到了就返回
		}
		cur = cur->next;
	}
	return NULL;
}

（6）在pos之后插入


//在pos之后插入
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
 
	SLTNode* newNode = BuySLTNode(x);//插入需要先创建结点
	newNode->next = pos->next;//新节点的下一个指向pos的下一个
	pos->next = newNode;//pos的下一个指向新节点
}

（7）在pos之前插入x


//在pos之前插入x
void SListInsertBefore(SLTNode** pplist, SLTNode* pos, SLTDataType x)
{
	assert(pos);
 
	SLTNode* newNode = BuySLTNode(x);
 
	//第一个节点就是pos，即头插
	if (pos == *pplist)
	{
		newNode->next = pos;
		*pplist = newNode;
	}
	else
	{
		SLTNode* prev = NULL;//用来记录pos的前一个结点
		SLTNode* cur = *pplist;
 
		while (cur != pos)//找pos
		{
			prev = cur;
			cur = cur->next;
		}
 
		newNode->next = cur;//新节点的下一个指向pos，此时跳出while循环的cur=pos
		prev->next = newNode;//前一个结点的下一个指向新节点
	}
}

（8）在pos之前插入x，没有头(plist)：后插一个值为x的节点，再跟前面的结点值交换


//在pos之前插入x，没有头(plist)的情况:后插一个值为x的节点，再跟前面的结点值交换。
void SListInsertBeforeNoHead(SLTNode* pos, SLTDataType x)
{
	assert(pos);
 
	SLTNode* newNode = BuySLTNode(x);
 
	//后插新节点
	newNode->next = pos->next;
	pos->next = newNode;
 
	//将新结点的值和pos的值进行交换
	SLTDataType temp = pos->data;
	newNode->data = temp;
	pos->data = x;
}

（9）删除后一个结点


//删除后一个节点
void SListEraseAfter(SLTNode* pos)
{
	assert(pos);
 
	if (pos->next == NULL)
	{
		return;
	}
	SLTNode* next = pos->next;
	pos->next = next->next;//pos的下一个指向pos的下一个结点的下一个结点
	free(next);
	next = NULL;
}

（10）删除当前位置


//删除当前位置
void SListEraseCur(SLTNode** pplist, SLTNode* pos)
{
	assert(pos);
	SLTNode* prev = NULL;
	SLTNode* cur = *pplist;
	while (cur != pos)//寻找pos
	{
		prev = cur;
		cur = cur->next;
	}
	prev->next = cur->next;//前一个结点的下一个指向当前结点即pos的下一个
	free(cur);
	cur = NULL;
}

025-test.c 测试代码


#define  _CRT_SECURE_NO_WARNINGS  1
#include<stdio.h>
#include<assert.h>
 
#include "025-SList.h"
 
void TestSList1()
{
	SLTNode* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
 
	SListPrint(plist);
 
	SListPushFront(&plist, 0);
	SListPrint(plist);
 
	SListPopBack(&plist);
	SListPrint(plist);
	SListPopBack(&plist);
	SListPrint(plist);
	SListPopBack(&plist);
	SListPrint(plist);
	SListPopBack(&plist);
	SListPrint(plist);
	
}
void TestSList2()
{
	SLTNode* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPrint(plist);
 
	SListPopFront(&plist);
	SListPopFront(&plist);
	SListPopFront(&plist);
	SListPopFront(&plist);
	SListPopFront(&plist);
	SListPrint(plist);
}
 
void TestSList3()
{
	SLTNode* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPrint(plist);
 
	SLTNode* pos = SListFind(plist, 3);
	if (pos)
	{
		//单链表查找兼具修改功能
		pos->data = 100;
		printf("找到了\n");
	}
	else
	{
		printf("没找到\n");
	}
 
	SListPrint(plist);
}
 
void TestSList4()
{
	SLTNode* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPrint(plist);
 
	SLTNode* pos = SListFind(plist, 3);
	SListInsertAfter(pos, 300);
	SListPrint(plist);
 
	SListInsertBefore(&plist, pos,400);
	SListPrint(plist);
 
	SListEraseCur(&plist, pos);
	SListPrint(plist);
}
 
int main()
{
	TestSList4();
 
	return 0;
}

执行结果：

链表应用OJ题

1.删除链表中等于给定值val的所有节点，OJ链接

分析：

（1）要删除某一结点，需要保存该结点的前一个结点（删除当前节点后，前一结点应指向当前结点的下一结点），同时需要保存当前结点的下一结点（删除当前结点后，能够继续向后访问该链表）

（2）操作：

遍历链表，如果当前结点值==val，就保存当前结点的下一个结点，前一结点指向当前结点的下一结点，释放当前结点，当前结点指向下一结点；

如果当前结点值!=val，前一结点挪到当前结点位置，当前结点挪到下一结点位置。需要考虑特殊情况，第一个结点值 == val时，此时prev=NULL需要特殊处理。

不带哨兵位头结点解法：


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeElements(struct ListNode* head, int val){
 
    struct ListNode* prev = NULL;
    struct ListNode* cur = head;
 
    while(cur)
    {
        if(cur->val == val)//找到了
        {
            struct ListNode* next = cur->next;//要free(cur)，就必须要先保存cur的下一个结点，否则无法继续访问下一结点
            if(prev == NULL)//cur是头，要删除的结点在第一个位置
            {
                free(cur);
                head = next;
                cur = next;
            }
            else
            {
                prev->next = next;
                free(cur);
                cur = next;
            }   
        }
        else
        {
            prev = cur;
            cur = cur->next;    
        }
      
    }   
    return head;
}

带哨兵位头结点解法：


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode* guardHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    guardHead->next = head;
 
    struct ListNode* prev = guardHead;
    struct ListNode* cur = head;
 
    while (cur)
    {
        if (cur->val == val)
        {
            struct ListNode* next = cur->next;
            prev->next = next;
            free(cur);
            cur = next;
        }
        else
        {
            prev = cur;
            cur = cur->next;
        }
    }
 
    head = guardHead->next;
    free(guardHead);
    guardHead = NULL;
    return head;
 
}

2.反转一个单链表 OJ链接

分析：

解法一：如果只定义两个节点，当n2指向n1时，n2的下一个结点就找不到了。因此要定义3个节点，n1和n2用于翻转，n3用于迭代：n1指向NULL，n2指向n1，n3用于记录n2的下一个结点。


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head)
{
    if(head == NULL || head->next == NULL)
    {
        return head;
    }
    
    struct ListNode* n1 = NULL,*n2 = head,*n3 = head->next;
    while(n2)
    {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if(n3)
        {
            n3 = n3->next;
        }
    }
    return n1;
}

解法二：头插法，依次取原链表中的节点头插到新节点


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* cur = head;
    struct ListNode* newHead = NULL;
 
    while(cur)
    {
        struct ListNode* next = cur->next;
 
        cur->next = newHead;
        newHead = cur;
        cur = next;
    }
    return newHead;
}

3.链表的中间结点 OJ链接

分析：只能遍历一遍，可以用快慢指针，慢指针每次走一步，快指针每次走两步


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 
struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* slow = head;
    struct ListNode* fast = head;
 
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
 
    return slow;
}

4.输出链表倒数第k个结点，OJ链接

分析：如何找倒数第k个结点，可以使用快慢指针，让快指针先走k步，再让慢指针开始走，此时快慢指针相差k步，然后快慢指针一起向后移动，等快指针移动到链表末尾NULL时，慢指针的位置就是倒数第k个结点位置。


struct ListNode 
{
	int val;
	struct ListNode *next;
};
 
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) 
{
    
    if(pListHead == NULL)
    {
        return NULL;
    }
 
    struct ListNode* slow = pListHead;
    struct ListNode* fast = pListHead;
    
    while(k--)
    {
        if(fast == NULL)
        {
            return NULL;
        }
        fast = fast->next;
    }
    
    while(fast)
    {
        slow = slow->next;
        fast = fast->next;
    }
    
    return slow;
}

5.合并两个有序链表 OJ链接

分析：尾插法，找第一个结点小的链表当作新表头，找尾比较麻烦，需要遍历，因此直接定义一个尾节点tail，每次让tail指向刚插入的节点，当有一个链表走完时就停下，再把没走完的链表全部连接到tail上。


struct ListNode {
    int val;
    struct ListNode *next;
};
 
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
{
 
    struct ListNode* head,*tail =  NULL;
    if(l1 == NULL)
    {
        return l2;
    }
    if(l2 == NULL)
    {
        return l1;
    }
 
    if(l1->val < l2->val)
    {
        head = tail = l1;
        l1 = l1->next; 
    }
    else
    {
        head = tail = l2;
        l2 = l2->next; 
    }
 
    while(l1 && l2)
    {
        if(l1->val < l2->val)
        {
            tail->next = l1; 
            l1 = l1->next;
            tail = tail->next; 
        }
        else
        {
            tail->next = l2;
            l2 = l2->next;
            tail = tail->next;
        }
    }
 
    if(l1 == NULL)
    {
        tail->next = l2;
    }
    else
    {
        tail->next = l1;
    }
 
    return head;
 
}

6.编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 OJ链接

分析：申请两个链表，一个放比x小的节点，一个放比x大的节点，最后将大链表链接在小链表末尾即可。


 
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
 
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // 有头指针
        struct ListNode* lessHead,* lessTail,*greaterHead,*greaterTail;
        lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode));
        greaterHead = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode));
        
        lessTail->next = NULL;
        greaterTail->next = NULL;
        
        struct ListNode *cur = pHead;
        
        while(cur)
        {
            if(cur->val<x)
            {
                lessTail->next = cur;
                lessTail = lessTail->next;
            }
            else
            {
                greaterTail->next = cur;
                greaterTail = greaterTail->next;
            }
            cur = cur->next;
        }
        
        lessTail->next = greaterHead->next;
        greaterTail->next = NULL;
        
        pHead = lessHead->next;
        free(lessHead);
        free(greaterHead);
        
        return pHead;
    }
};

7.链表的回文结构 OJ链接

分析：判断链表是否是回文结构，可以结合前面的题：

（1）利用快慢指针找到链表中间结点

（2）将后半部分逆置

（3）将（2）中的链表从第一个节点开始和中间结点开始同时进行访问，如果所有val相等，则链表为回文结构。


struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
 
struct ListNode* middleNode(struct ListNode* head)
    {
        // write code here
        struct ListNode* slow = head;
        struct ListNode* fast = head;
 
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
 
        return slow;
        
    }
    
    struct ListNode* reverseList(struct ListNode* head)
    {
        struct ListNode* cur = head;
        struct ListNode* newHead = NULL;
 
        while(cur)
        {
            struct ListNode* next = cur->next;
 
            cur->next = newHead;
            newHead = cur;
            cur = next;
        }
        return newHead;
    }
    
    bool chkPalindrome(ListNode* A) 
    {
        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;
    }

8.输入两个链表，找出它们的第一个公共结点 OJ链表

分析：判断链表是否相交，是判断是否有两个节点地址相同，而不是判断是否有两个结点值相同。

（1）若只是判断两个链表是否相交，直接判断最后一个链表是否相等即可

（2）要找出相交的结点：

a.计算两个链表的长度，计算两个链表的长度差距

b.让长链表先走差距步，再让两个链表同时向前走，若有相同的结点即相交。


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    if(headA == NULL || headB == NULL)
    {
        return NULL;
    }
 
    struct ListNode *curA = headA, *curB = headB;
 
    int lenA = 0,lenB = 0;
    
    while(curA->next)
    {
        curA = curA->next;
        lenA++;
    }
 
    while(curB->next)
    {
        curB = curB->next;
        lenB++;
    }
 
    if(curA != curB)
    {
        return NULL;
    }
 
    struct ListNode *longList = headA,*shortList = headB;
    if(lenA < lenB)
    {
        longList = headB;
        shortList = headA;
    }
 
    int gap = abs(lenA - lenB);
    while(gap--)
    {
        longList = longList->next;
    }
 
    while(longList != shortList)
    {
        longList = longList->next;
        shortList = shortList->next;
    }
 
    return longList;
}

9.给定一个链表，判断链表中是否有环 OJ链接

分析：

如何判断链表是否有环：使用快慢指针，慢指针一次走1步，快指针一次走2步，如果链表带环，那么快慢同时从链表起始位置开始向后走，一定会在环内相遇，此时快慢指针都有可能在环内打圈，直到相遇；否则，如果链表不带环，那么快指针会先走到链表末尾，慢指针只能在链表末尾追上快指针。


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

如果快指针不是一次走2步，而是一次走3步，一次走4步一次走x步呢？能不能判断出链表是否带环呢？

如果快指针一次走两步，当slow从直线中间移动到直线末尾时，fast又走了slow的2倍，因此当slow进环时，fast可能在环的任意位置，具体要看直线有多长，环有多大。在环内，一定是fast追slow，因为fast比slow移动的快。

fast一次走3步：假设slow进环的时候，fast跟slow相差N步，环的长度为C，追击时，slow走1步，fast走3步，每走1次，差距就缩小2，如下图所示：

因此对于N，如果N为奇数，一定不会相遇，差距为：N,N-2,N-4,···,1,-1(-1即C-1，一直是fast在追slow)

如果N为奇数，一定会相遇，差距为：N,N-2,N-4,···,2,0

那么根据以上推论，如果fast一次走4步，如果N为奇数，差距为：N,N-3,N-6,···,4,1,-2，如果N为奇数，差距为：N,N-3,N-6,···,5,2,-1

总结：如果slow进环时，slow和fast的差距N是奇数，且环的长度C为偶数(则C-1为奇数，上面举例可以看出差距最小为1或-1)，那么就永远追不上了。

10.给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 NULL OJ链接

如何求环的入口点？假设起点到入口点的距离是L，假设相遇点到入口点的距离是X，假设环的大小是C，相遇时，快指针已经在环内打转了N圈，那么慢指针走的路程为L+X，快指针走的路程为L+N*C+X，则有以下公式恒成立：

根据以上公式，则有L=N*C-X。因此，如果让快指针从相遇点出发，慢指针从起点出发，它们会在入口点相遇，此时快指针已经在圈内打转了N圈，快指针走的路程为N*C-X，慢指针走的路程为L。


struct ListNode {
    int val;
    struct ListNode *next;
};
 
struct ListNode* detectCycle(struct ListNode* head)
{
    struct ListNode* slow = head;
    struct ListNode* fast = head;
 
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
 
        if (slow == fast)
        {
            struct ListNode* meet = fast;
 
            while (meet != head)
            {
                meet = meet->next;
                head = head->next;
            }
 
            return meet;
        }
    }
 
    return NULL;
}

11.给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。要求返回这个链表的深度拷贝。OJ链接

（1）next如何处理?直接将结点拷贝下来是有问题的，把7拷贝下来指向的还是原来的13，而不是新创建的结点13，虽然值都是13，但是地址却不同。

所以要malloc之后，把值拷贝出来，然后把拷贝结点7的next指向原结点13。

（2）拷贝节点的random如何处理？如果直接处理，效率太低

a.拷贝以后，新链表需要确定每个random，需要去链表中查找，时间复杂度是O(N)，每个random都要处理就是O(N*N)，效率低

b.如果链表中存在节点的值相同，那么就更复杂了，比如有多个节点的值是7，那么原链表random有几个指向7的节点呢？新链表的random分别对应哪个7呢？毕竟各个7的地址不同。

把拷贝结点链接在原结点的后面，当找到原结点13的random结点7就能找到原结点7的拷贝结点，因为拷贝结点就是链接在原结点的后面，原结点13的random指向原结点7，拷贝结点13的random指向拷贝结点7。拷贝结点的random等于原结点random的next，即找到原结点就找到拷贝结点了。

（3）不能先让原结点7指向拷贝7，否则原结点7找不到原结点13了，应该让原结点7的copy结点7指向原结点7的next结点13。


/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */
struct Node* copyRandomList(struct Node* head)
{
    if (head == NULL)
    {
        return NULL;
    }
 
    //1.将拷贝结点挂在原结点后面，建立对应关系
    struct Node* cur = head;
 
    while (cur)
    {
 
        struct Node* next = cur->next;
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;
        cur->next = copy;
        copy->next = next;
        cur = next;
 
    }
 
    //2.处理copy结点的random
    cur = head;
    while (cur)
    {
        struct Node* copy = cur->next;
        if (cur->random == NULL)
        {
            copy->random = NULL;
        }
        else
        {
            copy->random = cur->random->next;
        }
        cur = copy->next;
 
    }
 
    //3.将拷贝结点取下来链接到一起，恢复原链表
    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;
    }
 
    struct Node* guard = copyHead;
 
    copyHead = copyHead->next;
    free(guard);
 
    return copyHead;
}

12.链表的插入排序 OJ链接


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 
struct ListNode* insertionSortList(struct ListNode* head)
{
	//1.初始条件
	struct ListNode* sortHead = head;
	struct ListNode* cur = head->next;
	sortHead->next = NULL;
 
	while(cur)//2.终止条件
	{
		//3.迭代条件
		struct ListNode* next = cur->next;
 
		//将cur结点插入到前面有序区间
		struct ListNode* p = NULL, * c = sortHead;
		while(c)
		{
			if(cur->val < c->val)
			{
				break;
			}
			else
			{
			p = c;
			c = c->next;
			}
		}
 
		if(p == NULL)
		{
 
			cur->next = c;
			sortHead = cur;
		}
		else
		{
		p->next = cur;
		cur->next = c;
		}
 
		cur = next;
	}
	return sortHead;
}

顺序表和链表优缺点对比

顺序表

链表

优点

1.按下标随机访问

2.CPU高速缓存命中率高

1.按需申请内存，不存在空间浪费

2.任意位置O(1)时间内插入删除数据

缺点

1.空间不够需增容（性能消耗及空间浪费）

2.头部或中间插入删除数据，需要挪动数据，效率低，时间复杂度O(n)

1.不支持下标随机访问

2.访问数据需要遍历，时间复杂度O(N)

顺序表和链表是相辅相成的，互相弥补对方的缺点，需要用顺序表还是链表存储数据，具体是看场景。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/黑客灵魂/article/detail/806982