c语言数据结构——如何学好链表?教你一招(初级)

前言

其实很多编程语言都差不多的,编程无非就是语法的熟练运用,清晰逻辑思路以及各种极端情况的考虑。不过博主说“无非”二字有点太过轻巧,毕竟自个儿也才是一个半斤八两的小东西,但是既然是要写博客,那么底气就得拿出来。

链表有个最重要的点就是需要有清晰的逻辑思路,那么该怎么做到呢?画图!!!画图!!!画图!!!,换句话来说只要你能够把逻辑思路用图的方式画出来,各种问题也就能够迎刃而解。

说道问题问题,那么链表当然也逃离不了练习题目,说白了,想要提升一门技能的经验值,最快的方法也就是实践,多实践你才能真实的感受其中的奥妙,所以博主特地为大家带来了几道非常经典的练习题,可以这么说,如果你能够熟练的掌握这些题目的解法、思路以及原理,那在链表上面你就非常棒啦~

题目

序号 题目 难度 链接 方法
1 删除单链表给定值的所有节点 简单 LeetCode 双指针
2 反转单链表 简单 LeetCode 三指针或头插双指针
3 取单链表的中间结点 简单 LeetCode 快慢双指针
4 取单链表的倒数结点 简单 牛客网 双指针
5 合并单链表 简单 LeetCode 带哨兵位的尾插法
6 排序单链表 简单 牛客网 带哨兵位的尾插法
7 对称单链表 简单 牛客网 双指针+逆置
8 相交单链表 简单 LeetCode 普通的遍历求解
9 环形单链表 简单 LeetCode 快慢双指针

删除单链表给定值的所有节点

c语言数据结构——如何学好链表?教你一招(初级)_第1张图片

这个题对于入门链表来说是比较适合的,这里需要考虑的一个关键问题是删除结点后,将上一个结点指向下一个结点,再用一个指针存储前一个结点,也就是常用的双指针用法。如下:

c语言数据结构——如何学好链表?教你一招(初级)_第2张图片
这样就完成了一次删除,接下来我们需要考虑指针cur到什么时候结束呢?

c语言数据结构——如何学好链表?教你一招(初级)_第3张图片
如上图所示,显而易见当cur为空指针的情况结束,到这里思路就基本上出来了。但是一些极端情况并没有考虑进去,如果一开始头结为head就为NULL,那么你对它解引用的时候当然会报错,所以我们要把这一点考虑进去。如下:

	if (head == NULL)
		return head;

另外我们是将head赋值给cur,而prev置空,那么我们还需要考虑一种情况,就是如果开头就出现了我们要删除的结点,会出现状况呢?如下:
c语言数据结构——如何学好链表?教你一招(初级)_第4张图片
prev->next = cur???,prev空指针能解引用吗?,所以我们必须将这个情况也考虑进去。也就是当这种情况发生的时候cur与head一起移动,而prev不变,仍指向空指针。

c语言数据结构——如何学好链表?教你一招(初级)_第5张图片

整体代码如下:

typedef struct ListNode Node;
struct ListNode* removeElements(struct ListNode* head, int val)
{
	//考虑头结点为空的情况
	if (head == NULL)
		return head;
	Node* prev = NULL;
	Node* cur = head;
	while (cur)
	{

		if (cur->val == val)
		{
			{		
				//考虑头结点为删除点的情况
				if (cur == head)
				{
					Node* delete = cur;
					cur = cur->next;
					free(delete);
				}
				else
				{
					Node* delete = cur;
					cur = cur->next;
					prev->next = cur;
					free(delete);
				}
			}
		}
		else
		{
			prev = cur;
			cur = cur->next;
		}
	}
	return head;
}

反转单链表

c语言数据结构——如何学好链表?教你一招(初级)_第6张图片
为什么这些网站或者是企业喜欢出单链表的题目呢?因为缺陷多的一批,如果是数组的话这个反转单链表就会变得异常简单。所以正是因为单链表缺陷多好出题,也好整崩我们这些小朋友的心态,但是做这些题目不也恰巧锻炼了我们的思维吗?所以凡事也是需要多角度思考的。

这个题如果用双指针是否可行呢?

c语言数据结构——如何学好链表?教你一招(初级)_第7张图片
我们先设置指针cur,next,如图所示,很明显我们可以看出来,当next->next时3和4的联系被断开了,那么就没有办法继续遍历了,这也恰巧告诉我们了另一种方法,我在加一个nextnext指针指向下一个数值,这样就可以继续遍历了,也就是三指针反转,如下:

c语言数据结构——如何学好链表?教你一招(初级)_第8张图片
但遍历到什么情况下循环体结束呢?这里有三个指针所以我们也不得不注意结束的情况。

c语言数据结构——如何学好链表?教你一招(初级)_第9张图片

显然是next为空指针的时候结束,但是nextnext为空指针的时候我们不得不结束它,但是这我们发现最后一次4和5并没有交换啊而是直接退出循环体了,怎么办呢?有一个很好的解决办法,在循环体内定义nextnext。

另外这个题目必须拥有一个结点以上才能进行遍历,这样的特殊极端情况也需要考虑进去。

代码如下

typedef struct ListNode Node;
struct ListNode* reverseList(struct ListNode* head)
{
	//两个结点以下直接返回
	if (head == NULL || head->next == NULL)
	{
		return head;
	}
	Node* cur = NULL;
	Node* next = head;
	while (next)
	{
		Node* nextnext = next->next;
		//反转
		next->next = cur;
		//遍历
		cur = next;
		next = nextnext;
	}
	return cur;
}

其实这个还有另一个方法头插法,这里就不为大家详细介绍了,但是关键点还是需要建立一个指针newHead,来实现头插,代码如下:

typedef struct ListNode Node;
struct ListNode* reverseList(struct ListNode* head)
{
	Node* newHead = NULL;
	Node* cur = head;
	while (cur)
	{
		Node* next = cur->next;

		//头插
		cur->next = newHead;
		newHead = cur;

		cur = next;
	}
	return newHead;
}

取单链表的中间结点

c语言数据结构——如何学好链表?教你一招(初级)_第10张图片
这个题目如果连续遍历两遍的话,第一遍求链表长度,第二遍找中间值,这样题目会变得异常简单,但是那我也没有办法达到一个锻炼的目的,那么博主在这里问大家,如果只遍历一次是否能够完成求解呢?答案是当然可以,这就涉及到一个新的双指针用法:快慢指针,慢指针slow走一步,快指针fast走两步,那么是不是fast到终点的时候slow才走完了整个数组的一半呢?如图:

c语言数据结构——如何学好链表?教你一招(初级)_第11张图片
乍一看,貌似确实当fast->next为NULL时,slow指针已经到了正中间,但是如果是偶数个结点呢?

c语言数据结构——如何学好链表?教你一招(初级)_第12张图片
题目要求如果是偶数个结点则返回中间第二个结点,但是这里结束条件则是fast=NULL,貌似偶数和奇数结点的结束条件不同,我们该如何将它们写在一个循环表达式里,用一个条件表达式判断呢?其实也不难发现

while(fast && fast->next)
{

}

这样问题是不迎刃而解了哇,但是这里我们需要注意的是fast必须放在fast->next的前面,我们首先要知道(1)&&(2)逻辑与运算的特点是:只要(1)不满足条件是不会执行(2)的,所以我们如果调换了顺序可能会发生解引用(fast为空指针的话)出错。

整体代码如下:

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

取单链表的倒数结点

c语言数据结构——如何学好链表?教你一招(初级)_第13张图片
同样如果遍历两遍链表,这个题目也非常简单,但是如果只遍历一遍是否能够解决问题呢?仔细想想,用双指针的办法能不能实现,如果取倒数第二个结点,,我们将第一个指针cur不动,第二个指针next先走二步,诶,那么之后cur与next共同移动的时候,是不是当next为空的时候,正好cur指向的是倒数第二个结点呢?

c语言数据结构——如何学好链表?教你一招(初级)_第14张图片
这个方法挺巧妙的,说实话一开始想不到也挺正常的,毕竟接触的比较少,但是你用心做过一遍这个题目的话,其实要想到也不难。

但其实这个题目有个陷阱,咱们想想如果倒数第k个结点的k值比结点还大是不是就无法得出结果了,所以写代码的时候,这一点也不得不考虑进去。

typedef struct ListNode Node;
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k)
{
	if (pListHead == NULL || pListHead->next == NULL)
	{
		return pListHead;
	}
	Node* cur = pListHead;
	Node* next = pListHead;
	//next向前走k步,如果结点比k少,直接返回NULL
	while (k-- && next)
	{
		next = next->next;
	}
	//为什么是k!=-1而不是k!=0,因为条件表达式k--执行了一次
	if (k != -1 && next == NULL)
	{
		return NULL;
	}
	while (next)
	{
		cur = cur->next;
		next = next->next;
	}
	return cur;
}

合并单链表

c语言数据结构——如何学好链表?教你一招(初级)_第15张图片
这个就是比大小然后依次尾插就可以了,但是尾插得有头结点才能开始插嘛,建立头这里提供两个方法,第一个就是l1与l2的头结点进行比较,取其小值当头结点。而博主重点讲的是第二种方法:带哨兵位的头结点尾插法

c语言数据结构——如何学好链表?教你一招(初级)_第16张图片

c语言数据结构——如何学好链表?教你一招(初级)_第17张图片
c语言数据结构——如何学好链表?教你一招(初级)_第18张图片
随机建立一个新的一个空间,来进行尾插,这样问题就会变得比较简单,代码的实现也比较容易。

代码如下:

typedef struct ListNode Node;
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
{
	Node* newHead = NULL;
	Node* newTail = NULL;
	newHead = newTail = (Node*)malloc(sizeof(Node));
	//依次排序
	while (l1 && l2)
	{
		if (l1->val > l2->val)
		{
			newTail->next = l2;
			newTail = l2;
            l2 = l2->next;
		}
		else
		{
			newTail->next = l1;
			newTail = l1;
            l1 = l1->next;
		}
	}
	//把剩下的全部链在新链表里
	if (l1 == NULL)
	{
		newTail->next = l2;
	}
	else
	{
		newTail->next = l1;
	}
    Node* head = newHead->next;
    free(newHead);
    newHead = NULL;
	return head;
}

排序单链表

在这里插入图片描述
示例如下

c语言数据结构——如何学好链表?教你一招(初级)_第19张图片
这题目我们也是有带哨兵位的头结点来解决这个问题,如下:

c语言数据结构——如何学好链表?教你一招(初级)_第20张图片
创建两个带哨兵位的头结点依次尾插便可,最后再将lessTail->next插入greatHead->next即可,代码如下

typedef struct ListNode Node, ListNode;
class Partition 
{
public:
ListNode* partition(ListNode* pHead, int x)
{
	if (pHead == NULL || pHead->next == NULL)
	{
		return pHead;
	}
	Node *lessHead, *lessTail;
	Node *greatHead, *greatTail;
	greatHead = greatTail = (Node*)malloc(sizeof(Node));
	lessHead = lessTail = (Node*)malloc(sizeof(Node));
	while (pHead)
	{
		if (pHead->val < x)
		{
			lessTail->next = pHead;
			lessTail = pHead;
		}
		else
		{
			greatTail->next = pHead;
			greatTail = pHead;
		}
		pHead = pHead->next;
	}
	lessTail->next = NULL;
	greatTail->next = NULL;
	lessTail->next = greatHead->next;
	Node* newHead = lessHead->next;
	free(lessHead);
	free(greatHead);
	return newHead;
}
};

注意因为牛客网给的是c++形式,但实际上我们是可以用c语言完成代码的编写的,也就是c++兼容c。

对称单链表

c语言数据结构——如何学好链表?教你一招(初级)_第21张图片
这个题目比较有意思,回文结构,我们可以先用快慢指针找到中间结点,如果是偶数个则为中间第二个结点,然后使用第一题的反转单链表,再进行逐一遍历比较值的大小即可,如下:

c语言数据结构——如何学好链表?教你一招(初级)_第22张图片

诶?为什么指针slow前面还需要一个指针prev啊?我们仔细想想一个问题,虽然slow是逆置了,但是slow前一位结点的next指向空指针了吗?显然没有,那么为了能够让它置空,我们需要保存前一个结点的地址,即创建prev。

代码如下:

typedef struct ListNode Node;
struct ListNode* reverseList(struct ListNode* head)
{
	//两个结点以下直接返回
	if (head == NULL || head->next == NULL)
	{
		return head;
	}
	Node* cur = NULL;
	Node* next = head;
	while (next)
	{
		Node* nextnext = next->next;
		//反转
		next->next = cur;
		//遍历
		cur = next;
		next = nextnext;
	}
	return cur;
}
class PalindromeList
{
public:
	bool chkPalindrome(ListNode* A)
	{
		Node* prev = NULL;
		Node* newHead = A;
		Node* slow = A;
		Node* fast = A;
		while (fast && fast->next)
		{
			prev = slow;
			slow = slow->next;
			fast = fast->next->next;
		}
		prev->next = NULL;
		//千万注意将指针传入进去的是指针存放的地址,而不是指针的地址。
		//是一份临时拷贝
		//如果不是二级指针接受,返回的时候需要slow来接受返回地址。
		//好好想想,千万注意。
		slow = reverseList(slow);
		while (newHead && slow)
		{
			if (newHead->val != slow->val)
				return false;
			newHead = newHead->next;
			slow = slow->next;
		}
		return true;
	}
};

相交单链表

c语言数据结构——如何学好链表?教你一招(初级)_第23张图片
这个题博主并没有更好的办法,目前博主想到的就是遍历求其AB链表的长度,然后用将长的那一个链表先走x步,x为AB链表长度之差,然后在一起遍历一起走,如果两指针的地址相同则返回该结点的地址。

c语言数据结构——如何学好链表?教你一招(初级)_第24张图片
代码如下:

typedef struct ListNode Node;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
	if (headA == NULL || headB == NULL)
		return NULL;
	int lA = 0;
	int lB = 0;
	Node* shortLlist = headA;
	Node* longList = headB;
	Node* curA = headA;
	Node* curB = headB;
	while (curA)
	{
		lA++;
		curA = curA->next;
	}
	while (curB)
	{
		lB++;
		curB = curB->next;
	}
	//只要判断是否lA大于lB即可
	//因为最前面的赋值的默认情况是lB大于lA
	if (lA > lB)
	{
		shortLlist = headB;
		longList = headA;
	}
    int gap = abs(lA-lB);
    while(gap--)
    {
        longList = longList->next;
    }

	while (shortLlist && longList)
	{
		if (shortLlist == longList)
			return longList;
		shortLlist = shortLlist->next;
		longList = longList->next;

	}
	return NULL;

}

环形单链表

c语言数据结构——如何学好链表?教你一招(初级)_第25张图片

这个题目相对来说比较简单,没有让你去判断入环点,而只是需要你判断他是否为环,快慢指针能够很好的解决这一问题,但是!我们需要考虑的一点是,为什么这两个指针一定会相遇呢?证明如下:

c语言数据结构——如何学好链表?教你一招(初级)_第26张图片
代码如下:

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

链表的简单题暂且到这告一段落,这些题目给博主自己的感受也颇深,希望大家看后,可以自己独立分析,独立写代码,独立找bug,完成这些题目。 有什么问题也希望大家多多指正哦~~~

你可能感兴趣的