反转链表 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

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

再调用一次递归函数

reverseListRecursive(head.next);

直接从宏观的角度上看,肯定是将head.next之后的所有节点都反转过来了,就像下图所示,其中1被挡住了不要在意。

重点来了,如何将最后的节点2指向节点1,并将节点1指向空?

其实用两行代码实现即可,将head.next(节点2).next(NULL)指向节点1,也就是 = head即可

然后再将节点1指向空,也即head.next = null;

 head.next.next = head;
 head.next = null;

力扣答案总结:

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

/**
 * @Author: 翰林猿
 * @Description: 反转链表
 **/
public class ReverseListNode {
    //非递归方式
    public ListNode reverseList(ListNode head) {
        //初始化三个指针,其中latter要在过程中指定,因为有可能cur为空,导致latter为空
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode latter = cur.next;
            //将cur指向pre
            cur.next = pre;
            //三个指针都向后移动,其中pre和cur在这里移动,latter在第一句会自行移动。
            pre = cur;
            cur = latter;
        }
        return pre;
    }
    //递归方式
    public ListNode reverseListRecursive(ListNode head) {
        if (head == null || head.next==null)
            return head;
        ListNode rev = reverseListRecursive(head.next);     //最后会获取到head
        head.next.next = head;
        head.next = null;
        return rev;
    }
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
​
        ListNode node = new ReverseListNode().reverseList(head);
        System.out.println("反转后的第一个节点值应当为5 = "+node.val);
​
        ListNode node2 = new ReverseListNode().reverseListRecursive(head);
        System.out.println("递归反转后的第一个节点值应当为5 = "+node.val);
    }
}
​
​
class ListNode {
    int val;
    ListNode next;
    ListNode() {
    }
    ListNode(int val) {
        this.val = val;
    }
    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

热门相关:仙城纪   特工重生:快穿全能女神   法医娇宠,扑倒傲娇王爷   法医王妃不好当!   夫人你马甲又掉了