反转链表

📣可以直接在 LeetCode 上练习：206. 反转链表 - 力扣（Leetcode）

思路 ​

🧠定义 p 指针遍历链表，将 p 指针经过的节点头插到链表。

假设我们有这么一个单向链表：

graph LR
	a[head] --> 1
	1 --> 2
	2 --> 3
	3 --> b[NULL]

(1) 定义 P 指向 head (2) head 指向 null

此时，其实我们有两个链表：

graph LR
	a[head] --> b[NULL]
	c[P] --> 1
	1 --> 2
	2 --> 3
	3 --> d[NULL]

(3) p->next 头插到 head 作为头指针的链表 (4) p = p->next

此时，链表数据为：

graph LR
	a[head] --> 1
	1 --> b[NULL]
	c[P] --> 2
	2 --> 3
	3 --> d[NULL]

再次执行 3 ~ 4 步骤：

graph LR
	a[head] --> 2
	2 --> 1
	1 --> b[NULL]
	c[P] --> 3
	3 --> d[NULL]

重复 3 ~ 4 步骤就能将原链表逆置过来。

代码实现 ​

int ReverseLinkedlist(linkedlist l) {
	if (l == NULL || l->len == 0)
		return -1;
	linkedlist p = l->next;
	l->next = NULL;
	while (p != NULL) {
		linkedlist q = p;
		p = p->next;

		q->next = l->next;
		l->next = q;
	}
}

为什么没有调用insert_head进行头插呢？因为这个插入函数会创建新的节点，进行插入，而在这里可以使用原有的节点来插入（毕竟逆置不会有新节点产生对吧）。

• leetcode_206_反转链表