链表逆置 C 语言

创建所需的相关结构体

1
2
3
4
5
struct List
{
	int date;
	struct List* next;
};

首先我们创建一个函数用于创建链表的。

建立创建链表的函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct List* writeList()
{
	struct List* head = NULL, * current = NULL, * prev = NULL;
	int data;
	while (~scanf("%d", &data) && data != 0)//0为标记输入结束
	{
		current = (struct List*)malloc(sizeof(struct List*));
		if (head == NULL)
			head = current;
		else
			prev->next = current;
		current->date = data;
		current->next = NULL;
		prev = current;
	}
	return head;
}

我们有了链表当然也得有个输出链表内部数据的函数，来验证查看我们链表内的内容。

建立打印链表内容的函数

1
2
3
4
5
6
7
8
9
10
void printList(struct List* L)
{
	struct List* p = L;
	while (p)
	{
		printf("%d", p->date);
		p = p->next;
	}
	printf("\n");
}

当然链表申请了内存空间我们就得释放内存空间

建立释放内存空间的函数

1
2
3
4
5
6
7
8
9
10
11
void freeList(struct List* head)
{
	struct List* freeNode;

	while (NULL != head)
	{
		freeNode = head;
		head = head->next;
		free(freeNode);
	}
}

开始正题。

链表逆置

首先我们要明白什么是链表逆置，链表逆置顾名思义，链表的表头和表位改变，打个比方如果链表就是一列火车的话链表逆置以后火车头变成火车尾，第二节车厢会变成倒数第二节车厢，第三节车厢变成倒数第三节车厢以此类推最后火车尾变成火车头。如图所示：

实现逆置的方法

迭代实现逆置

链表迭代逆置的时候需要借助三个指针，这里我们把三个指针定义为 bigin,mid,end 这三个并让他们分别指向如图所示。

begin 指针指向初始化为空 null，mid 指针指向初始化为链表头 head，end 指针指向初始化为第二节点。

准备工作做好了现在就可以开始一个节点一个节点的逆置了。

第一步：mid 指针指向的节点的指针域要与 begin 相同。也就是 mid 指针指向的节点的指针域变成与 begin 相同的值 null。这样子链表第一节点也就是链表头会和其他节点分离出来。

第二步：每个指针都向后移动一个节点准备逆置下一个节点，也就是说 begin 指针指向原链表第一节点也就是头节点，mid 指针指向原链表第二节点，end 指针指向原链表第三节点。
上述步骤可以看下面的解析图。

继续上述操作。

第一步：mid 指针指向的节点的指针域要与 begin 相同也就是指向原链表第一节点原链表的链表头。

第二步：每个指针都向后移动一个节点准备逆置下一个节点。这个时候 begin 指针指向原链表第二节点，mid 指针指向原链表第三节点，end 指针指向原链表第四节点。

如图所示：

继续。

第一步：mid 指针指向的节点的指针域要与 begin 相同也就是指向原链表第二节点。

第二步：每个指针都向后移动一个节点准备逆置下一个节点。这个时候 begin 指针指向原链表第三节点，mid 指针指向原链表第四节点，end 指针指向原链表第四节点的指针域也就是 null。因为原链表已经没有了第五节点所以第四节点就是链表的表尾。

具体步骤解析如图所示。

到了这一步不难发现现在离完成逆置很接近了。接下来我们只需要改变 mid 指针的指向和 head 头指针的指向就好了。

第一步：mid 指针指向的节点的指针域要与 begin 相同也就是指向原链表第三节点。

第二步：这一次我们不需要移动 begin，mid，end 三个指针了，现在我们只需要改变 head 头指针的指向就好了，head 头指针的指向改为和 mid 指针相同。

以下为解析图：

到了这里我们的链表就已经逆置完毕了，这就是用迭代方法逆置链表。

代码实现如下（C 语言）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//迭代逆置法，head 为无头节点链表的头指针
struct List* iteration_reverseList(struct List* head)
{
	if (head == NULL || head->next == NULL)
		return head;
	else
	{
		struct List* beg = NULL;
		struct List* mid = head;
		struct List* end = head->next;
		//一直遍历
		while (1)
		{
			//mid指针指向节点的指针域要与beg指针指向一样
			mid->next = beg;
			//判断 end 是否为 NULL，如果成立则已经找到原链表尾，退出循环
			if (end == NULL)
				break;
			// beg，mid，end三个指针都向后移动一个节点准备逆置下一个节点
			beg = mid;
			mid = end;
			end = end->next;
		}
		//最后head头指针的指向改为和mid指针相同。
		head = mid;
		return head;
	}
}

递归逆置链表

递归逆置法和迭代逆置法的思想恰好相反，递归逆置法的实现思想是从链表的尾节点开始，依次向前遍历，遍历过程依次改变各节点的指向，即另其指向前一个节点。

递归理解起来要比迭代难一点，我们先附上实现代码，然后一一讲解。

样例代码（C 语言）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct List* recursion_reverseList(struct List* head)
{
	if (head == NULL || head->next == NULL)
	//空链表或者只有一个节点的时候直接返回头指针就好了，因为逆置没有意义。
	/*当然这个也是我们递归的出口，
	如果找到最后一个节点的时候开始向外层层退出*/
		return head;
	else
	{
		//递归内入，原链表被分成多个子链表，直到最后一个节点。最后一个节点也会被分成只有一个链表头的子链表
		struct List* new_head = recursion_reverseList(head->next);
		/*在每一层递归中head指针指向的节点的下一个节点的指针域要与head指针指向要相同,
		这也就是在从子链表拆卸一个节点，接到正在逆置的链表后面。，例如head指向原链表的第二节点，
		此时第二节点接在原链表的第一节点，经过上面操作以后，原链表第二节点会被接在原链表第三节点后面，实现部分逆置。*/
		//做完上述操作后把当前head指针指向节点的指针域改为null，因为这个是当前我们已经逆置完的节点组成的子链表的链表尾。
		head->next->next = head;
		head->next = NULL;
		return new_head;
		/*new_head指针保存最后一个节点，也就是原链表尾，并一直向上一层返回，
		逆置后我们的原链表尾会变成逆置后的链表头，这个就是逆置后的链表头，一直向上返回能保证链表逆置完还能找到新的链表头*/
	}
}

接下来我们用图去一一分析递归逆置链表的过程。

刚开始函数向内递归链表被切成很多子链表。

现在开始递归向外层，一层一层退出。并进行子链表的逆置衔接。完成逆置。

头插法逆置链表

头插法比较好理解。在原有链表的基础上，依次将位于链表头部的节点摘下，然后采用从头部插入的方式生成一个新链表，则此链表即为原链表的逆置版。

具体操作如图

代码实现（C 语言）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct List* head_reverse(struct List* head)
{
	struct List* new_head = NULL;
	struct List* temp = NULL;//用于临时存储节点
	if (head == NULL || head->next == NULL)
		return head;
	while (head != NULL)
	{
		temp = head;
		//将 temp 从 head 中摘除
		head = head->next;
		//将 temp 插入到 new_head 的头部
		temp->next = new_head;
		new_head = temp;
	}
	return new_head;
}

就地逆置法逆置链表

就地逆置法和头插法的实现思想类似，唯一的区别在于，头插法是通过建立一个新链表实现的，而就地逆置法则是直接对原链表做修改，从而实现将原链表反转。在原链表的基础上做修改，需要额外借助 2 个指针（假设分别为 beg 和 end）。

初始状态下， beg 指针 指向第一个节点，end 指针指向 beg->next，也就是原链表的第二节点。如下图：

接下来将 end 所指节点 2 从链表上摘除，然后再添加至当前链表的头部。如图所示。

我们继续上面的操作。

再来一次我们就完成逆置了。

最后我们就完成了链表的逆置。

代码实现（C 语言)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct List* local_reverse(struct List* head)
{
	struct List* beg = NULL;
	struct List* end = NULL;
	if (head == NULL || head->next == NULL)
		return head;
	beg = head;
	end = head->next;
	while (end != NULL)
	{
		//将 end 从链表中摘除
		beg->next = end->next;
		//将 end 移动至链表头
		end->next = head;
		head = end;
		//调整 end 的指向，另其指向 beg 后的一个节点，为反转下一个节点做准备
		end = beg->next;
	}
	return head;
}

原文地址 blog.csdn.net