面试必备|单链表反转思路图形解析

01

—

单链表

链表玩的是指针操作，非常容易出错，尽管看似很简单。

先定义一种单链表，JAVA（或C#）描述的数据结构如下：

public class CLinkedList { public int val { get; set; } //简化起见，数据域直接定义为 int public CLinkedList next { get; set; } //next域，这就是链到下一个元素，或者理解为下一个元素的引用 }

再用最易理解的方式，初始化一个含有3个元素的链表，

CLinkedList mylist = new CLinkedList(); mylist.val = 1; mylist.next = new CLinkedList() { val = 2, next = new CLinkedList() { val = 3, next = null } };

图形化显示如下：

02

—

一种反转算法

我们试着将一个单链表反转，定义Reverse(list) API，实现此功能，比如对上面那个简单的链表，执行Reverse后的效果如下所述，当然颜色我们没有反转。

怎么实现呢？提供一种空间复杂度为O(1)，时间复杂度为O(n)的算法。基本的实现思路如下：

1. 创建一个新的节点newhead，其val为原链表头结点的val，其next为 null
2. 定义next，指向原链表的第二个节点（头结点的next节点）
3. 遍历，条件为： next != null: var tmpnext = next.next; //标记下next的next，为什么？接下来要破坏它，但是还要用它，所以标记它 next.next = newhead; // 当前的即将成为新链表头节点的next指向即将为旧的头节点newhead newhead = next; // newhead指向新构造的链表头节点，这样新链表成功增加了一个节点 next = tmpnext; //为下轮迭代做准备

4. 返回 newhead

03

—

反转算法图形显示

我们试着将一个单链表反转，定义Reverse(list) API，实现此功能，比如对如下链表进行反转操作：

算法图形化表达出来，步骤1和2的图形：

步骤3的图形显示过程，全部罗列：

• 执行：tmpnext = next.next 后，

• 执行：next.next = newhead 后，

• 执行 newhead = next 后，此时newhead指向的链表增加了一个节点（就是next节点），2--->1的链表

• 执行 next = tmpnext 后，next指向下一个添加到新链表头部的节点，即3节点。

再次走一遍上述的过程后，节点3又添加到2--->1这个链表上，newhead依然指向反转后的链表的头部，反转后的链表：3-->2--->1.

思路总结

• next变量始终指向原链表的即将要添加到反转链表的节点，
• newhead始终指向反转链表的头。
• 每遍历一次，newhead增加一个节点，即next节点，直到next变为null为止。