反转链表 Java版 图文并茂思路分析带答案(力扣第206题) | 您所在的位置:网站首页 › 力扣反转链表 › 反转链表 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; } } |
CopyRight 2018-2019 实验室设备网 版权所有 |