什么是倒排链表？leetcode链表原创问答图

反向链表是程序员必须具备的基本素质，在面试和笔试时经常出现。总觉得求逆链表的代码不太好理解，所以决定抄袭leetcode的经典求逆链表题，用十多张图来分析。希望加深大家对链表反转的理解。感谢您的阅读。

leetcode的逆向链表原创问答

标题说明：逆向单向链表。

1. 输入：1->2->3->4->5->NULL
2. 输出：5->4->3->2->1->NULL

分析：

假设有一个链表1→2→3→Ø，我们想把它改为Ø←1←2←3。元素。由于节点没有对其前一个节点的引用，因此必须预先存储其前一个元素。在更改引用之前，需要另一个指针来存储下一个节点。不要忘记在最后返回新的标头引用！

代码实现：

1. public ListNodeverseList(ListNode head) {
2. ListNode prev = null;
3. ListNode curr = head;
4. while (curr != null) {
5. ListNode nextTemp = curr.next;
6. curr.next = prev;
7. prev = curr;
8. curr = }Temp; return prev;
9. }

链表反转代码实现图解

接下来我们对上面的代码实现进行说明。首先在上面的实现代码中添加行号如下：

1. public ListNode reverseList(ListNode head) { //1
2. ListNode prev = null; // 2
3. ListNode curr = head; // 3
4. while (curr != null) { //4
5. ListNode nextTemp = curr.next; //5
6. curr.next = 上一个; // 6
7. prev = curr; //7
8. curr = nextTemp; //8
9. }
10. 之前返回； //9
11. }

第一行代码图

1. public ListNode reverseList(ListNode head) { //1

us 根据标题描述的意思，我们假设链表有1 2，或者3个元素，后面跟一个null，由于输入的是ListNode Head，所以即将反转的链表如下：

第二行代码图解？链表的头被赋值给Curr，即Curr指向头链表。如下图：

循环代码图解

1. while (curr != null) { //4
2. ListNode nextTemp = curr.next; // 5
3. curr.next = 上一个; // 6
4. prev = curr; //7
5. curr = nextTemp; //8
6. }

循环部分是反转的链表的核心部分。让我们首先浏览一下循环并以图形方式对其进行分析。

因为curr指向head，head不为空，所以进入循环。 我们先看第5行：

1. ListNode nextTemp = curr.next; //5

将curr.next赋值给nextTemp变量，即nextTemp指向curr的下一个节点（即节点2），可以形象如下：

然后在第6行执行：

1. curr.next = 上一个； // 6

将prev赋值给curr.next，那么prev初始化指向null，即curr(Node 1)指向null，链表图如下：

然后我们看到上面的执行第 7 行

1. prev = curr; //7

将Curr赋值给Prev，Prev指向Curr，示意图如下：

然后退出到第8行：

1. curr = nextTemp; //8

将nextTemp赋值给Curr，即Curr指向nextTemp。示意图如下：

至此，第一个循环执行结束， return 时，到了循环条件，curr 仍然不为零，我们再进一步说明一下。

再次执行5-8行代码，即可依次获取图像：

1. ListNode nextTemp = curr.next; //5
2. curr.next = 上一个; // 6
3. prev = curr; //7
4. curr = nextTemp; //8

执行ListNodenextTemp=curr.next;:

执行curr=v.n

执行prev后=当前； :

执行完curr=nextTemp;ee curr 仍然不为空，所以返回到 While 循环中再次执行：

1. ListNode nextTemp = curr.next ; //5
2. curr.next = 上一个; // 6
3. prev = curr; //7
4. curr = nextTemp; //8

可以按顺序得到图像：​​这里我们发现curr已经为零了，可以跳出循环了。此时prev指向链表的反转，所以执行到第9行后，就实现了反转链表功能：

1. return prev； //9

作者：捡蜗牛的小男孩