初阶3 链表

标签：初阶 ListNode struct next 链表 phead cur

本章重点

链表
链表OJ题
链表与顺序表区别

1.链表

1.1 链表的概念及结构

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

结构：

注意:

从上图可看出，链式结构在逻辑上是连续的，但是在物理上不一定连续
现实中的结点一般都是从堆上申请出来的
从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续
链表使用时,不用断言(用NULL判断使用结束)

1.2 链表分类

请添加图片描述

可以看出这三种分类最多可以结合处8个不同类型的单链表

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

1.3 单链表的实现

1.3.1 结点的定义

typedef int SLTDataType;
 
typedef struct SlistNode
{
	SLTDataType data;
	struct SlistNode* next;
}SLTNode;

1.3.2 函数的声明、实现与详解

声明

// 动态申请一个结点
SLTNode* BuySLTNode(SLTDataType x);//返回类型是：SLTnode* 结构体地址

//单链表打印
void SListPrint(SLTNode* phead);

//尾插，尾删
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);

//头插，头删
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopFront(SLTNode** pphead);

//查找一个数，返回其地址
SLTNode* SListFind(SLTNode* phead, SLTDataType x);

//在单链表pos之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x);

//在pos之前插入,因为在前面插入会改变phead的指针，所以需要传双指针
void SLTInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x);

//删除pos位置的节点
void SLTErase(SLTNode** pphead, SLTNode* pos);

//删除pos后的节点
void SLTEraseAfter(SLTNode* pos);

//单链表的释放：
void SLTDestroy(SLTNode** pphead);

实现

1. 动态申请一个结点
SLTNode* BuySLTNode(SLTDataType x)
{
		SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
		if (newnode == NULL)
		{
			perror("malloc fail");
			exit(-1);
		}
	 
		newnode->data = x;
		newnode->next = NULL;
	 
		return newnode;
}
malloc申请一个动态结点，如果malloc调用失败，返回NULL则直接结束掉程序

成功，赋值，并返回
2. 打印单链表
void SListPrint(SLTNode* phead)
{
		SLTNode* cur = phead;
		while (cur != NULL)
		{
			printf("%d->", cur->data);
			cur = cur->next;
		}
		printf("NULL\n");
}
传函数头结点的地址，并用cur进行接收，以防止phead的值被改变，从而导致该链表找不到头
3. 尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
		SLTNode* newnode = BuySLTNode(x);
		if (*pphead == NULL)
		{
			*pphead = newnode;
		}
		else
		{
			SLTNode* tail = *pphead;
			while (tail->next != NULL)
			{
				tail = tail->next;
			}
			tail->next = newnode;
		}
}
注意 : tail->next = newnode; 不是 tail = newnode;
此外*pphead = newnode;用二级指针
而tail->next = newnode;没有
因为后者(即:结构体成员)在操作时,用的已经是地址了

这里传递双指针的原因是：如果要改变头结点的数据，需要2次传参，就需要用双指针

（你要改变int，传int的地址int*，你要改变int*，就要传递int*的地址int**）

改变之前地址就要用地址的地址去进行

（下面的函数传参中，需要改变头结点的数据时，都需要用双指针）

用newnode接受一个新的结点，然后判断结点是否为空，空则直接赋值，不为空则找处尾结点的地址再进行链接
4. 尾删
void SLTPopBack(SLTNode** pphead)
{
		assert(*pphead);
		if ((*pphead)->next == NULL)
		{
			free(*pphead);
			*pphead = NULL;
		}
		else
		{
			SLTNode* tail = *pphead;
			while (tail->next->next)
			{
				tail = tail->next;
			}
			free(tail->next);
			tail->next = NULL;
		}
}
如果链表为空，则不能再进行删除，用assert断言判断一下
要删掉尾节点，就要找到尾结点的前一个结点，将前一个结点的->next=NULL
所以再找的时候找的时tail->next->next，然后将tail->next=NULL
这样写的话，如果该单链表只有一个数，tail->next->next不存在，则代码就会出现错位
所以要加上一个判断，用(*pphead)->next == NULL来判断该单链表时否只有一个结点。

正确写法也可以这样写：

先定义一个prev，tail再最后一个，prev再tail的前一个，如果tail为空，直接让prev的next为空即可(注意只有一个数据的情况)
//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(*pphead);
	SLTNode* tail = *pphead;
	SLTNode* prev = NULL;
	while (tail->next)
	{
		prev = tail;
		tail = tail->next;
	}
	if (prev)
	{
		free(tail);
		prev->next = NULL;
	}
	else
	{
		free(tail);
		*pphead = NULL;
	}
}
5. 头插和头删
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
		SLTNode* newnode = BuySLTNode(x);
		newnode->next = *pphead;
		*pphead = newnode;
}

void SLTPopFront(SLTNode** pphead)
{
		assert(*pphead);
		SLTNode* Next = (*pphead)->next;
		free(*pphead);
		*pphead = Next;
}
头插和头删是单链表主要的优势，又快又简单
6. 查找一个数，返回其地址
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
		SLTNode* cur = phead;
		while (cur)
		{
			if (cur->data == x)
			{
				return cur;
			}
			cur = cur->next;
		}
		return NULL;
}
用cur等于phead防止phead改变，找到返回cur，未找到，返回NULL
7. 在单链表pos之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
		assert(pos);
		SLTNode* newnode = BuySLTNode(x);
		newnode->next = pos->next;
		pos->next = newnode;
}
先用newnode的next指向pos的next
再让pos的next指向newnode
8. 在pos之前插入,因为在前面插入会改变phead的指针，所以需要传双指针
void SLTInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
		assert(pos);
		if (pos == *pphead)//如果在头节点前插入就相当于头插
		{
			SLTPushFront(pphead, x);
		}
		else
		{
			SLTNode* prev = *pphead;
			while (prev->next != pos)
			{
				prev = prev->next;
			}
			SLTNode* newnode = BuySLTNode(x);
			newnode->next = prev->next;
			prev->next = newnode;
		}
}
在之前插入，我们的插入可能在1之前，也就是要改变头节点，相当于头插，就需要二级指针
是头插，直接调用头插函数就行

先找到pos的前一个，我们定义一个prev，prev->next=pos时，即可在中间插入newnode
9. 删除pos后的节点
void SLTEraseAfter(SLTNode* pos)
{
		assert(pos);
	 
		if (pos->next == NULL)//只有一个头节点
		{
			return;
		}
		else
		{
			SLTNode* nextNode = pos->next;
			pos->next = nextNode->next;
			free(nextNode);
		}
}
和插入一样，只有一个头节点要单独处理
10. 删除pos位置的节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
		assert(pos);
		assert(pphead);
	 
		if (pos == *pphead)
		{
			SLTPopFront(pphead);
		}
		else
		{
			SLTNode* prev = *pphead;
			while (prev->next != pos)
			{
				prev = prev->next;
			}
			prev->next = pos->next;
			free(pos);
		}
}
先用prev来表示前一个，当prev->next=pos时，进行删除
11. 单链表的释放：
void SLTDestroy(SLTNode** pphead)
{
   SLTNode* cur = *pphead;
   while (cur)
   {
   	SLTNode* nextnode = cur->next;
   	free(cur);
   	cur = nextnode;
   }
   *pphead = NULL;
}
单链表不像顺序表，需要一次一次进行释放

如果先释放了1，就找不到后面的结点了
所以先要定义一个next或者nextnode来接受cur的下一个结点
然后再free，最后将nextnode赋值给cur

最后将*pphead置为NULL
不用一级指针,因为无法改变phead的值(外部)

1.4 带头双向循环链表的实现

1.4.1 带头双向循环链表的声明

typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;
}LTNode;
 
// 创建返回链表的头结点.
LTNode* BuyListNode(LTDataType x);
 
//初始化
LTNode* ListInit();
 
// 双向链表打印
void LTPrint(LTNode* phead);
 
// 双向链表尾插
void LTPushBack(LTNode* phead, LTDataType x);
// 双向链表尾删
void LTPopBack(LTNode* phead);
 
// 双向链表头插
void LTPushFront(LTNode* phead, LTDataType x);
// 双向链表头删
void LTPopFront(LTNode* phead);
 
// 双向链表查找
ListNode* LTFind(LTNode* phead, LTDataType x);
 
// 双向链表在pos的前面进行插入
void LTInsert(LTNode* pos, LTDataType x);
// 双向链表删除pos位置的结点
void LTErase(LTNode* pos);
 
//判空
bool LTEmpty(LTNode* phead);
 
//判断链表的大小size
size_t LTSize(LTNode* phead);
 
// 双向链表销毁
void LTDestory(LTNode** phead);

1.4.2 接口函数的实现

1. 创建返回链表的头结点

LTNode* BuyListNode(LTDataType x)
{
   LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
   if (newnode == NULL)
   {
   	perror("malloc fail");
   	exit(-1);
   }
   
   newnode->data = x;
   newnode->next = NULL;
   newnode->prev = NULL;
   
   return newnode;
}

2. 初始化

带头双向循环链表
当链表为NULL的状态是：

带头循环链表是逻辑最复杂的，但是实现起来是最简单的和实用的
LTNode* ListInit()
{
   LTNode* phead = BuyListNode(-1);
   phead->next = phead;
   phead->prev = phead;
   
   return phead;
}
由于初始化需要改变结构体，就需要用的二级指针

但因为有头结点的存在，其他接口函数上是不会改变结构体的，所以都用一级指针

为了统一好看一点，我们初始化也用一级指针

那我们就可以用返回值的方式进行处理
3. 打印
void LTPrint(LTNode* phead)
{
   assert(phead);
   
   LTNode* cur = phead->next;
   while (cur != phead)
   {
   	printf("%d->", cur->data);
   	cur = cur->next;
   }
   printf("\n");
}
4. 尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
   assert(phead);
   LTNode* node = BuyListNode(x);
   
   node->next = phead;
   node->prev = phead->prev;
   
   phead->prev->next = node;
   phead->prev = node;
}
5. 尾删
void LTPopBack(LTNode* phead)
{
   assert(phead);
   assert(phead->next != phead);
   
   LTNode* tail = phead->prev;
   
   phead->prev->prev->next = phead;
   phead->prev = phead->prev->prev;
   
   free(tail);
}
6. 头插
void LTPushFront(LTNode* phead, LTDataType x)
{
   assert(phead);
   
   LTNode* node = BuyListNode(x);
   
   node->next = phead->next;
   node->prev = phead;
   
   phead->next = node;
   node->next->prev = node;
}
要先将newnode链接到下一个结点，再将phead连接到newnode上

需要注意顺序
7. 头删
void LTPopFront(LTNode* phead)
{
   assert(phead);
   assert(phead->next != phead);
   
   LTNode* first = phead->next;
   LTNode* second = first->next;
   
   /*phead->next = second;
   second->prev = phead;*/
   phead->next->next->prev = phead;
   phead->next = phead->next->next;
   
   free(first);

}
8. 查找
ListNode* LTFind(LTNode* phead, LTDataType x)
{
   assert(phead);
   
   LTNode* cur = phead->next;
   while (cur != phead)
   {
   	if (cur->data == x)
   	{
   		return cur;
   	}
   	cur = cur->next;
   }
   return NULL;
}
9. 在pos的前面进行插入
void LTInsert(LTNode* pos, LTDataType x)
{
   assert(pos);
   
   LTNode* prev = pos->prev;
   LTNode* newnode = BuyListNode(x);
   
   prev->next = newnode;
   newnode->prev = prev;
   newnode->next = pos;
   pos->prev = newnode;
}
插入的实现可以直接让头插和尾插进行复用，

尾插的复用：LTInsert(phead,x);

头插的复用：LTInsert(phead->next,x);
10. 删除pos位置的结点
void LTErase(LTNode* pos)
{
   assert(pos);
   
   LTNode* Prev = pos->prev;
   LTNode* Next = pos->next;
   free(pos);
   
   Prev->next = Next;
   Next->prev = Prev;
}
删除的实现也可以让尾删和头删复用，

尾删的复用：LTErase(phead->prev);

头删的复用：LTErase(phead->next);
11. 判空
bool LTEmpty(LTNode* phead)
{
   assert(phead);
   
   /*if (phead->next == phead)
   	return true;
   else
   	return false;*/
   
   return phead->next == phead;
}
12. 判断链表的大小size
size_t LTSize(LTNode* phead)
{
   assert(phead);
   
   size_t size = 0;
   LTNode* cur = phead->next;
   while (cur != phead)
   {
   	size++;
   	cur = cur->next;
   }
   return size;
}
1.用哨兵位头节点data来记录size（有点小问题）
有的时候我们可以在哨兵位头节点里面的data存放size的大小，这样做的话，在进行插入和删除的时候，需要加上phead->data++和phead->data–
这需要用int的时候才能有，单如果是其他的，比如char，如果链表长度超过128就会出现问题

2.可以直接在结构里面加个size变量

3.直接遍历，如上：
13. 双向链表销毁
void LTDestory(LTNode** pphead)
{
   assert(pphead);
   
   LTNode* cur = *pphead;
   cur = cur->next;
   while (cur != *pphead)
   {
   	LTNode* Next = cur->next;
   	free(cur);
   	cur = Next;
   }
   
   free(*pphead);
   *pphead = NULL;
}
这里由于*pphead=NULL要改变结构体，所以需要用二级指针

这里想要整体统一的话，就需要外部进行置空，需要使用者进行

2.单链表的OJ题

2.1 移除链表元素

struct ListNode* removeElements(struct ListNode* head, int val) 
{
   struct ListNode* cur=head;
   struct ListNode* prev=NULL;
   while(cur)
   {
       if(cur->val!=val)
       {
           prev=cur;
           cur=cur->next;
       }
       else
       {
           if(prev)//防止第一个元素为 val
           {
               prev->next=cur->next;
               free(cur);
               cur=prev->next;
           }
           else
           {
               head=cur->next;
               free(cur);
               cur=head;
           }
           
       }
   }
   return head;
}

或

struct ListNode* removeElements(struct ListNode* head, int val) 
{
   struct ListNode* cur=head;
   struct ListNode *newhead=NULL, *tail=NULL;

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

2.2 反转一个单链表

思路1：

创建一个新的链表，将原链表的值头插进新的链表，并返回即可

struct ListNode* reverseList(struct ListNode* head)
{
   struct ListNode*newhead=NULL;//创建新的链表
   struct ListNode*tmp=NULL;//记录cur的next
   struct ListNode*cur=head;
   while(cur)
   {
       tmp=cur->next;
       //头插
       cur->next=newhead;
       newhead=cur;
       cur=tmp;
   }
   return newhead;
}

思路2：

用1指向空，2指向1…
需要用三个指针进行操作
用n1和n2进行指向的转换，n3记录下一个结点地址

struct ListNode* reverseList(struct ListNode* head)
{
  if(head==NULL)
   return NULL;
   struct ListNode*n1,*n2,*n3;
   n1=NULL;
   n2=head;
   n3=n2->next;
   while(n2)
   {
       n2->next=n1;

       n1=n2;
       n2=n3;
       if(n3)
           n3=n3->next;
   }
   return n1;
}

2.3 找到链表的中间结点

思路：

利用快慢指针，快指针每次走两步，满指针每次走一步，当快指针走到头时，满指针刚好走到中间
这里要分两种情况：单链表为奇数和单链表为偶数，
奇数时，快指针走到最后一个结点处，慢指针走到中间
偶数时，快指针走到NULL处，满指针走到中间的下一个
ListNode* middleNode(ListNode* head) 

{

struct ListNode *slow, *fast;
fast=slow=head;
//因为不知道链表时奇数还是偶数，所以用fast&&fast->next来判断
while(fast && fast->next)
{
fast=fast->next->next;
slow=slow->next;
}
return slow;
}

2.4 找到链表中倒数第k个结点

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

2.5 合并两个有序链表

思路:

创建一个新的链表，然后对原来的链表进行对比，数据小的，尾插进新的链表里面

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
   //判断链表是否为空
   if(list1==NULL)
   		return list2;
   if(list2==NULL)
   		return list1;
   if(list1==NULL || list2==NULL)
   		return NULL;
   
   //定义新的头来记录两个链表里面的数据
   struct ListNode*newhead=NULL,*tail=NULL;
   struct ListNode*cur1=list1,*cur2=list2;
   struct ListNode*n1=cur1->next,*n2=cur2->next;
   
   //确定新的链表的头是哪个
   if(cur1->val <= cur2->val)
   {
   	tail = cur1;
   	newhead = tail;
   	cur1 = n1;
   	if(cur1 != NULL)
   		n1 = n1->next;
   }
   else
   {
   	tail = cur2;
   	newhead = tail;
   	cur2 = n2;
   	if(cur2 != NULL)
   		n2 = n2->next;
   }
   
   //进行循环比较，当一个链表为空的时候退出循环
   while(cur1 && cur2)
   {
   	if (cur1->val <= cur2->val)
   	{
   		tail->next = cur1;
   		tail = tail->next;
   		cur1 = n1;
   		if (cur1 != NULL)
   			n1 = n1->next;
   	}
   	else
   	{
   		tail->next = cur2;
   		tail = tail->next;
   		cur2 = n2;
   		if (cur2 != NULL)
   			n2 = n2->next;
   	}
   }
   
   //判断哪个链表是空，然后将不是空的链表链接的新链表后面
   if (cur1 == NULL)
   {
   	while (cur2)
   	{
   		tail->next = cur2;
   		tail = tail->next;
   		cur2 = n2;
   		if (cur2 != NULL)
   			n2 = n2->next;
   	}
   }
   else
   {
   	while (cur1)
   	{
   		tail->next = cur1;
   		tail = tail->next;
   		cur1 = n1;
   		if (cur1 != NULL)
   			n1 = n1->next;
   	}
   }
   return newhead;
}

或(使用哨兵卫)

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
   
   //定义新的头来记录两个链表里面的数据
   struct ListNode *guard=NULL, *tail=NULL;
   struct ListNode *cur1=list1, *cur2=list2;
   guard= tail = (struct ListNode*)malloc(sizeof(struct ListNode))
   tail->next = NULL;
 
   
   //进行循环比较，当一个链表为空的时候退出循环
   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 = cur->next;
   	}
   }
   
   //判断哪个链表是空，然后将不是空的链表链接的新链表后面
   if (cur1)
   {
   	tail->next = cur1;
   }
   if (cur2)
   {
   	tail->next = cur2;
   }
   struct ListNode* head = guard->next;
   free(guard);
   return head;
}

2.6 链表分割

思路：

加上哨兵位的头节点进行处理
注意：要让greaterHead的最后一个数指向NULL不然会发生死循环\

ListNode* partition(ListNode* pHead, int x) 
{
   //定义四个变量，less里面放小于x的数，greater里面放大于x的数
   //Head里面存放该链表的头结点地址，Tail进行判断和插入
   struct ListNode* lessHead,*lessTail,*greaterHead,*greaterTail;
   //为这两个链表开辟一个哨兵位的头结点
   lessHead=lessTail = (struct ListNode*)malloc(sizeof(struct listNode));
   greaterHead=greaterTail = (struct ListNode*)malloc(sizeof(struct listNode));
   
   lessTail->next = greaterTail->next = NULL;
   
   struct listNode* cur = pHead;
   while(cur)//当cur为空时结束
   {
       if(cur->val < x)//小于x的尾插list链表里面
       {
           lessTail->next=cur;
           lessTail=lessTail->next;
       }
       else 
       {
           greaterTail->next=cur;
           greaterTail=greaterTail->next;
       }
       cur = cur->next;
   }
   //让小的链表尾的next指向大的链表的哨兵位头节点的next
   lessTail->next=greaterHead->next;
   //大数组的尾置空，以防止生成环
   greaterTail->next=NULL;
   //用phead指向lessHead的next完成
   pHead=lessHead->next;
   //最后释放两个哨兵头结点
   free(lessHead);
   free(greaterHead)
   return pHead;
}

2.7 链表的回文结构

思路：

回文就是两边对称
反转后半段，然后和前半段进行比较
- 借助之前的快慢指针找到中间节点，然后再进行头插反转
- 如果时偶数，直接进行判断就行，
- 如果是奇数，因为没有改变2的next，所以2的next还是3，依然可以进行判断，走到NULL结束即可

class PalindromeList 
{
public:
   //找出链表的中点
   struct ListNode* middleNode(ListNode* head) 
   {
       struct ListNode*slow,*fast;
       fast=slow=head;
       
       while(fast && fast->next)
       {
           fast=fast->next->next;
           slow=slow->next;
       }
       return slow;
   }
   //将链表反转
   struct ListNode* reverseList(struct ListNode* head)
   {
       struct ListNode*newhead=NULL;//创建新的链表
       struct ListNode*tmp=NULL;//记录cur的next
       struct ListNode*cur=head;
       while(cur)
       {
           tmp=cur->next;
           //头插
           cur->next=newhead;
           newhead=cur;
           cur=tmp;
       }
       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;
           A=A->next;
           rhead=rhead->next;
       }
       return true;
   }
};

2.8 相交链表找第一个公共结点

难点：

单链表，两个数组长度不同，要判断是否相交和找出相交结点

思路：

还是利用快慢指针，先算出两个数组的大小，相减差值的绝对值就是，快指针需要多走的结点
要计算处数组的大小，就需要遍历数组，同时也能找到尾结点，如果尾结点不相同
则说明这两个链表不相交，返回NULL
尾结点数相同就相交，尾结点不同就返回NULL，所以我们可以直接找尾直接用
while（cur->next）判断，之后如果有空链表，再前面加一步判断即可
否则，在快指针走了差值步之后，快慢指针一起走，直到两个指针相等时，就是这两个链表的交点位置
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
   struct ListNode*A=headA,*B=headB;
   int lenA=0,lenB=0;
   
   //找尾，计算每个链表的大小
   while(A->next)
   {
       lenA++;
       A=A->next;
   }
   while(B->next)
   {
       lenB++;
       B=B->next;
   }

   //尾结点不相等就不相交
   if(A!=B)
   {
       return NULL;
   }
   
   //计算差值，并找出长链表和短链表
   int gap=abs(lenA-lenB);
   struct ListNode*longlist = headA,*shortlist = headB;
   if(lenB>lenA)
   {
       longlist=headB;
       shortlist=headA;
   }

   //长链表走gap步
   while(gap--)
   {
       longlist=longlist->next;
   }

   //同时走，找交点
   while(longlist!=shortlist)
   {
       longlist=longlist->next;
       shortlist=shortlist->next;
   }

   return longlist;
}

2.9 环形链表1: 判断链表是否有环

思路：

快慢指针，fast走两步，slow走一步
当slow也走进环里面的时候，这是就会形成一个fast追slow的追击问题
只要fast和slow差一步，并且是个环，就一定会相遇
bool hasCycle(struct ListNode *head) {
   struct ListNode*fast=head,*slow=head;
   //这里也要判断fast->next是因为如果链表只有一个数，没有fast->next->next，就会出错
   while(fast && fast->next)
   {
       fast=fast->next->next;
       slow=slow->next;
       if(fast==slow)
           return true;
   }
   return false;
}

2.10 环形链表2: 如果有环，返回入环点

这个题主要是一个智力题，对代码能力的要求不大，主要是看你能不能想明白其中的道理
思路1

这里先说结果：

再相遇的时候，指针head重新从头走，指针meet从环的相遇点处走,在head与meet相遇的时候，这个点就是环的入口点

解释：

所以在圈很大的时候（特殊情况）
走的距离：慢指针=L+X，快指针=L+X+C
由快指针是满指针走的距离的2倍可以得到：2*（L+X）=L+X+C，C=L+X
可得出结论 : L = C - X
但是这只是一个特殊情况，不足以证明环小的时候
走的距离：慢指针=L+X，快指针=L+X*n+C
由快指针是满指针走的距离的2倍可以得到：2*（L+X）=L+X*n+C，C=L+X
可得出结论 : L = C*n - N 或 L = C*(n-1) + C-N
struct ListNode *detectCycle(struct ListNode *head) 
{
   struct ListNode*fast=head,*slow=head;
   //这里也要判断fast->next是因为如果链表只有一个数，没有fast->next->next，就会出错
   while(fast && fast->next)
   {
       fast=fast->next->next;
       slow=slow->next;
       if(fast==slow)
       {
           struct ListNode*meet =slow;
           //让头结点和meet一起走，找到他们相交的点
           while(head!=meet)
           {
               head=head->next;
               meet=meet->next;
           }
           return meet;
       }
   }
   return NULL;
}
思路2: 转换为链表相交

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
   struct ListNode*A=headA,*B=headB;
   int lenA=0,lenB=0;
   
   //找尾，计算每个链表的大小
   while(A->next)
   {
       lenA++;
       A=A->next;
   }
   while(B->next)
   {
       lenB++;
       B=B->next;
   }

   //尾结点不相等就不相交
   if(A!=B)
   {
       return NULL;
   }
   
   //计算差值，并找出长链表和短链表
   int gap=abs(lenA-lenB);
   struct ListNode*longlist = headA,*shortlist = headB;
   if(lenB>lenA)
   {
       longlist=headB;
       shortlist=headA;
   }

   //长链表走gap步
   while(gap--)
   {
       longlist=longlist->next;
   }

   //同时走，找交点
   while(longlist!=shortlist)
   {
       longlist=longlist->next;
       shortlist=shortlist->next;
   }

   return longlist;
}
struct ListNode *detectCycle(struct ListNode *head) 
{
   struct ListNode*fast=head,*slow=head;
   while(fast && fast->next)
   {
       fast=fast->next->next;
       slow=slow->next;
       if(fast==slow)
       {
           struct ListNode*meet =slow;
           struct ListNode*lt1 =meet->next;
           struct ListNode*lt2 =head;
           meet->next=NULL;
           return getIntersectionNode(lt1,lt2);
       }
   }
   return NULL;
}

2.11 复制带随机指针的链表

思路1：

可以利用相对位置求解，我们要找random指向的是第几个结点

就比如，先对7这个结点的random进行复制，就对数组进行一次遍历，遍历过程中记录num，该结点是第几个结点，当random指向的地址和遍历到的地址位置相同时，就返回num的值

在进行复制random的时候，就直接利用相对位置num进行复制

但是这样的话，得到的时间复杂度是O(n^2)

如果要求时间复杂度是O(n)的话，要怎么做？
思路2：

1.拷贝结点链接在源节点的后面：

2.设置拷贝结点的random

拷贝结点的random=cur的random的next

3.拷贝结点解下来，连接组成拷贝链表
代码（思路2的实现）：
struct Node* copyRandomList(struct Node* head) 
{
   //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.将源结点的random进行复制
   cur=head;
   while(cur)
   {
       struct Node*copy=cur->next;
       if(cur->random==NULL)
       {
           copy->random=NULL;
       }
       else
       {
           copy->random=cur->random->next;
       }
       cur=cur->next->next;
   }

   //3.将copy的在源节点后面的结点解下来放到一起
   cur=head;
   struct Node*CopyHead=NULL,*tail=NULL;
   while(cur)
   {
       struct Node*copy=cur->next;
       struct Node*Next=copy->next;
       cur->next=Next;
       
       //尾插
       if(CopyHead==NULL)
       {
           CopyHead=tail=copy;
       }
       else
       {
           tail->next=copy;
           tail=tail->next;
       }
       cur=Next;
   }
   return CopyHead;
}

链表与顺序表区别

不同点	顺序表	链表
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持O(1)	不支持：O(N)
任意位置插入或删除元素	可能需要搬移元素，效率低O(N)	只需修改指针指向
插入	动态顺序表，空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁
缓存利用率	高	低

顺序表:

优点:尾插尾删效率高,下标的随机访问快
缺点:空间不够需要扩容(扩容代价大);头部或者中间插入删除效率,需要挪动数据。

链表:

优点:需要扩容，按需申请释放小块节点内存;任意位置插入效率很高–O(1)。
缺点:不支持下标随机访问;

标签：初阶,ListNode,struct,next,链表,phead,cur
From： https://blog.csdn.net/ydm_ymz/article/details/144598408

1.链表

1.1 链表的概念及结构

1.2 链表分类

1.3 单链表的实现

1.3.1 结点的定义

1.3.2 函数的声明、实现与详解

1.4 带头双向循环链表的实现

1.4.1 带头双向循环链表的声明

1.4.2 接口函数的实现

2.单链表的OJ题

2.1 移除链表元素

2.2 反转一个单链表

2.3 找到链表的中间结点

2.4 找到链表中倒数第k个结点

2.5 合并两个有序链表

2.6 链表分割

2.7 链表的回文结构

2.8 相交链表找第一个公共结点

2.9 环形链表1: 判断链表是否有环

2.10 环形链表2: 如果有环，返回入环点

2.11 复制带随机指针的链表

相关文章

赞助商

阅读排行