反转链表 Java版 图文并茂思路分析带答案（力扣第206题） ...

反转链表

力扣第206题
我们不只是简单的学习（背诵）一个数据结构，而是要分析他的思路，以及为什么要有不同的指针等等
非递归方式：

思路分析：首先要链表有个头指针没有任何问题

然后，我们要将1的下一个节点指向空，这样才能将其反转过来，但是这个时候我们发现和下一个节点2失去了联系

所以我们要有一个指针，在1还没有将next指向空前，记录下2的位置。所以我们用一个next指针记录2。并为了好理解，将head改名为cur代表当前节点。

因此，我们只要将cur的指向下一个节点的指针指向空之后，便将cur和next指针同时向后移动。

不过这样我们发现，我们cur和前面的节点失去了联系，就不能将节点2指向1了，所以我们还要有一个指针负责记录前一个节点，我们就叫它pre吧，那么再来考虑pre指针最开始应该放在哪呢，其实只要指向最左边的那个NULL就好了。

因此我们刚刚是将1指向NULL，现在改成将cur指向pre即可，就像这样。

然后我们就可以将这三个指针都向后移动，重复上一步和本步操作，直到cur为null结束即可。

递归方式：

首先是写出递归的最后答案，也就是所谓的递归出口，毫无疑问是返回第一个节点head

1. if (head == null || head.next==null)
2.     return head;

复制代码

再调用一次递归函数

1. reverseListRecursive(head.next);

复制代码

直接从宏观的角度上看，肯定是将head.next之后的所有节点都反转过来了，就像下图所示，其中1被挡住了不要在意。
重点来了，如何将最后的节点2指向节点1，并将节点1指向空？

其实用两行代码实现即可，将head.next（节点2）.next（NULL）指向节点1，也就是 = head即可
然后再将节点1指向空，也即head.next = null;

1. head.next.next = head;
2. head.next = null;

复制代码

力扣答案总结：

我们来具体实现一下吧，其中的reverseList内的代码即是力扣答案

1. /**
2. * @Author: 翰林猿
3. * @Description: 反转链表
4. **/
5. public class ReverseListNode {
6.    //非递归方式
7.    public ListNode reverseList(ListNode head) {
8.        //初始化三个指针,其中latter要在过程中指定，因为有可能cur为空，导致latter为空
9.        ListNode pre = null;
10.        ListNode cur = head;
11.        while (cur != null) {
12.            ListNode latter = cur.next;
13.            //将cur指向pre
14.            cur.next = pre;
15.            //三个指针都向后移动,其中pre和cur在这里移动，latter在第一句会自行移动。
16.            pre = cur;
17.            cur = latter;
18.        }
19.        return pre;
20.    }
21.    //递归方式
22.    public ListNode reverseListRecursive(ListNode head) {
23.        if (head == null || head.next==null)
24.            return head;
25.        ListNode rev = reverseListRecursive(head.next);     //最后会获取到head
26.        head.next.next = head;
27.        head.next = null;
28.        return rev;
29.    }
30.    public static void main(String[] args) {
31.        ListNode head = new ListNode(1);
32.        head.next = new ListNode(2);
33.        head.next.next = new ListNode(3);
34.        head.next.next.next = new ListNode(4);
35.        head.next.next.next.next = new ListNode(5);
36. ​
37.        ListNode node = new ReverseListNode().reverseList(head);
38.        System.out.println("反转后的第一个节点值应当为5 = "+node.val);
39. ​
40.        ListNode node2 = new ReverseListNode().reverseListRecursive(head);
41.        System.out.println("递归反转后的第一个节点值应当为5 = "+node.val);
42.    }
43. }
44. ​
45. ​
46. class ListNode {
47.    int val;
48.    ListNode next;
49.    ListNode() {
50.    }
51.    ListNode(int val) {
52.        this.val = val;
53.    }
54.    ListNode(int val, ListNode next) {
55.        this.val = val;
56.        this.next = next;
57.    }
58. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！