数据结构：链表（经典算法例题）详解

目录

1.移除链表元素

2.反转链表

3.链表的中间结点

4.合并两个有序链表

5.环形链表的约瑟夫问题

6.分割链表

我以过客之名，祝你前程似锦

1.移除链表元素

（1）题目：

https://leetcode.cn/problems/remove-linked-list-elements/description/

（题目来源）

（2）解析：

这题的具体实现有两种思路

思路一：遍历链表，释放值为val的结点 

思路二：找值不为val的结点并将其尾插到新链表中

这题我为什么采用思路二而不采用思路一关键就是思路一虽然看上去简单粗暴，但它在实现过程中涉及了删除链表中元素的操作，这意味着对链表之间结点指向的修改更为麻烦而且伴随着容易遗忘释放内存而产生内存泄漏的风险，所有这里较优解还是思路二，无论是思路清晰度和实现操作的复杂度都比思路一要好些，以下就是思路二的具体实现代码：

#include<stdio.h>


  typedef struct ListNode 
  {
      int val;
      struct ListNode *next;
  }ListNode;
 
struct ListNode* removeElements(struct ListNode* head, int val) 
{
    //创建一个空链表
    ListNode* newHead;
    ListNode* newTail;
    newHead = newTail = NULL;

    //遍历原链表
    ListNode* pcur = head;
    while (pcur)
    {
        //找值不为val的结点，尾插入新链表
        if (pcur->val != val)
        {
            //链表为空
            if (newHead == NULL)
            {
                newHead = newTail = NULL;
            }
            //链表不为空
            else
            {
                newTail->next = pcur;
                newTail = newTail->next;//尾插：先将原尾结点的next指针改方向再改新尾结点（newTail这个结构体类型的指针的指向）
            }
        }
        pcur = pcur->next;
    }

//这里有两点值得注意，一就是如果程序仅仅运行到这里是不可以的，如果原链表最后一个数据也是val，代码到此为止是会在新链表最后插入这个val代表的结点的，具体原因我会在正文解释
    if (newTail)
   {
       newTail->next = NULL;
   }
       return newHead;
}

但在思路二插入链表的过程中有两点特别值得关注：

        一就是我在倒数第二行代码里所展示的，为什么要将newNode的next指针设置为空:这行代码预防的情况主要就是原链表最后一个结点的val值是我们想要排除的val值，因为在上述代码不断地遍历，尾插后，确实可以一定程度上将内容不是val的结点拎出来并插入一个新链表中，但是当我们遍历原链表至倒数第二个节点时，如果恰恰下一个结点的内容是val，我们上述的代码会不让这最后一个进入验证的循环，但最重要的是，上述代码也仅仅是没让它进入循环而已，最底层的关系中，倒数第二个结点的next指针依旧是指向这个原链表的最后一个的含有着val的结点，因此当原链表最后一个结点的val值是我们想要排除的val值时，上述代码依旧会输出这最后一个val，而这却不是我们想要看到的，因此及时止损（及时使倒数第二个结点的next指向空就显得非常重要了）

        二则是在写代码过程中对于各种不同情况的讨论，在这题里我们涉及到三处对空链表的验证，分别是传入pcur（原链表的头结点的指针）时，对代表着新链表的头结点的指针是否为空的验证以及最后对插入结束后对代表着尾结点的指针是否为空的验证，因为若不对这几个指针进行验证，程序运行后就无法避免的有可能遇见对空指针的解引用操作，而此类操作在C语言里是大忌

2.反转链表

（1）题目：

https://leetcode.cn/problems/reverse-linked-list/description/

（题目来源）

（2）解析：

同样，这里也有两种思路

思路一：创建新链表，遍历原链表，将原链表结点拿过来头插

思路二：创建3个结点，然后通过循环下列步骤改变各结点指向

以下是第二种思路的代码示例和一些注意点：

typedef struct ListNode 
{
	int val;
	struct ListNode* next;
	
}ListNode;

 ListNode* reverseList(struct ListNode* head)
{
	 //判空
	 if (head == NULL)
	 {
		 return head;
	 }
	 //创建三个指针
	 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;
}

这里主要有两个注意点：

        一是要注意对传入指针的判断（是否为空指针）

        二则是对n3范围的注意，也就是我倒数第二行对n3是否为空指针的判断，因为在我们一步一步的翻转过程中，n3势必要比n2快一步成为空指针，而当n2也成为空指针时，如果不对n3进行判断的话，出现就会进行对n3的解引用，也就是空指针的解引用

3.链表的中间结点

（1）题目：

https://leetcode.cn/problems/middle-of-the-linked-list/description/

（题目来源）

（2）解析：

两种思路

思路一：遍历，设置变量count来记录结点位置，直至返回（count/2）结点或其next结点

思路二：快慢指针（图解如下）

原理：2*slow=fast

具体代码：

typedef struct ListNode
{
	int val;
	struct ListNode* next;

}ListNode;

ListNode* middleNode(struct ListNode* head)
{
	//创建快慢指针
	ListNode* slow = head;
	ListNode* fast = head;
	while (fast && fast->)//注意判断顺序不能颠倒！
	{
		slow = slow->next;
		fast = fast->next->next;
	}
	//此时slow指向的即是我们想要的中间结点
	return slow;
}

这里有一点需要注意就是while循环的结束条件之所以有两个分别是对应了我在图解里画的两种情况，前一种表示fast的next指针为空时结束，后者则是表示fast指针本身不可以为空

4.合并两个有序链表

（1）题目：

https://leetcode.cn/problems/merge-two-sorted-lists/description/

（题目来源）

（2）解析：

以下为最后一步的两种情况（即 l1 先到NULL和 l2 先到NULL）

具体代码：

typedef struct ListNode
{
	int val;
	struct ListNode* next;

}ListNode;


ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
	if (list1 == NULL)
	{
		return list2;
	}
	if (list2 == NULL)
	{
		return list1;
	}


	ListNode* l1 = list1;
	ListNode* l2 = list2;

	ListNode* newHead, * newTail;
	newHead = newTail = NULL;

	while (l1 && l2)
	{
		if (l1->val < l2->val)
		{
			//l1拿下来尾插
			if (newHead == NULL)
			{
				newHead = newTail = l1;
			}
			else
			{
				newTail->next = l1;
				newTail = newTail->next;
			}
			l1 = l1->next;
		}
		else
		{
			//l2拿下来尾插
			if (newHead == NULL)
			{
				newHead = newTail = l2;
			}
			else
			{
				newTail->next = l2;
				newTail = newTail->next;
			}
			l2 = l2->next;

		}
	}
	//跳出循环有两种情况：l1先走到空，l2先走到空
	if (l1)
	{
		newTail->next = l2;
	}
	if (l2)
	{
		newTail->next = l1;
	}

	return newHead;
}

这里有几个重要的点：

       首先就是关于我在最上面对传入链表是否为空的讨论，这些其实并不是需要死记的东西，你看题目嘛，他的范围就明确了0的情况，也就是暗含了对空指针讨论的提示

        其次我想说的就是这个题目的具体解决方式：通过不断的对两个链表对应结点的依次比较，小的先尾插，最后分类讨论一下就行

         最后也就是最重要的还有有一点：即关于上述代码的改进

所以修改之后的代码如下：

typedef struct ListNode
{
	int val;
	struct ListNode* next;

}ListNode;


ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
	if (list1 == NULL)
	{
		return list2;
	}
	if (list2 == NULL)
	{
		return list1;
	}


	ListNode* l1 = list1;
	ListNode* l2 = list2;

	ListNode* newHead, * newTail;
	//newHead = newTail = NULL;
    newHead = newTail = (ListNode*)malloc(sizeof(ListNode));


	//改进之后：
	while (l1 && l2)
	{
		if (l1->val < l2->val)
		{
			//l1拿下来尾插
			newTail->next = l1;
			newTail = newTail->next;
			l1 = l1->next;
		}
		else
		{
			//l2拿下来尾插
		    newTail->next = l2;
		    newTail = newTail->next;
			l2 = l2->next;
		}
	}
	//跳出循环有两种情况：l1先走到空，l2先走到空
	if (l1)
	{
		newTail->next = l2;
	}
	if (l2)
	{
		newTail->next = l1;
	}

	return newHead->next;
}

同时这里还有两点需要注意：

        一.malloc申请空间之后哨兵位（也就是头结点本身存储的val值是系统给的一个随机值，只有newNode->next及之后的才是我们所求的链表，因此上述代码的返回值必须得从原来的return newHead变成return newHead->next）

        二.malloc之后必须要释放内存，但这里提交系统后后台会自动帮助我们释放内存，因此在正式的代码里，还必须加上以下几行来代替return newHead->next：

//动态申请的空间需要手动释放
ListNode* ret = newHead->next;
free(newHead);
newHead = NULL;
return ret;

5.环形链表的约瑟夫问题

（1）题目：

（2）解析：

以下是我对这道题的思考过程：

具体代码：

这道题其实跟上面讲的几道题大同小异，本质上其实也就是对链表中插入和删除元素的考察，画个图仔细看看其中各个指针的指向变化就很容易可以得出基本思路了，这道题的难点也是主要就在于主函数里对排除特殊情况的讨论，这点理解了之后其他的也就迎刃而解了

6.分割链表

（1）题目：

https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70

（题目来源）

（2）解析：

三种思路

思路一：原链表修改

思路二：新链表修改

         通过创建新链表，大于x的往前插，小于x的往后插，就此题来说是可以解出来的，但相比第一种不仅在顺序上会出现颠倒而且还涉及了尾插和头插两种链表操作方式，代码层面上相比思路一也要麻烦不少

思路三：创建两个带头链表

具体代码：

typedef struct ListNode
{
	int val;
	struct ListNode* next;

}ListNode;


ListNode* partition(ListNode* head, int x)
{

	if (head == NULL)
	{
		return head;
	}

	//创建两个带头链表
	ListNode* lessHead, * lessTail;
	ListNode* greaterHead, * greaterTail;
	lessHead = lessTail = (ListNode*)malloc(sizeof(ListNode));
	greaterHead = greaterTail = (ListNode*)malloc(sizeof(ListNode));

	//遍历原链表，将原链表中的结点尾插到大小链表中
	ListNode* pcur = head;
	while (pcur)
	{
		if (pcur->val < x)
		{
			//尾插到小链表中
			lessTail->next = pcur;
			lessTail = lessTail->next;
		}
		else
		{
			//尾插到大链表中
			greaterTail->next = pcur;
			greaterTail = greaterTail->next;
		}
		pcur = pcur->next;
	}
	//修改大链表的尾结点的next指向
	greaterTail->next = NULL;//给next指针初始化，若不加这一行，代码会出现死循环
	
	//使小链表的尾结点和大连表的第一个有效首结点相连（注意不是哨兵位）
	lessTail->next = greaterHead->next;

	//修改大链表的尾结点的next指针指向
	greaterTail->next = NULL;

	ListNode* ret = lessHead->next;
	free(lessHead);
	free(greaterHead);
	lessHead = greaterHead = NULL;
	return ret;
}

这题如果在自己写的时候很有可能会出现两类报错而导致程序无法成功通过oj测验的情况，下面我就来详细说说这两种报错：

第一类：超出时间限制

就像上图所示的，超出时间限制大部分全都是有代码陷入死循环导致的，这里的死循环形成原因就是虽然我们设置了大小链表并且分好类，但由于大链表尾结点的指向没有更改，它就会按原来的指向再指回原链表从而造成了链表的闭环，也就是我们这里所说的死循环

第二类：使用之前未初始化

这里发生错误的原因根本就在于在题目给定的结构体中因为不包含有对next指针的初始化：

从而导致上述情况验证时next指针自动默认产生了一个随机地址（可能会导致一些不安全的问题）因此解决办法就是确保这两行代码的先后顺序

好的，这些就是我想分享的几道题目了

全文终