【LeetCode】206、反转链表 Reverse Linked List

【LeetCode】206、反转链表 Reverse Linked List

反转链表不用多说了吧，考的频率太大了。

一、题目描述

题目地址

https://leetcode-cn.com/problems/reverse-linked-list/

二、小白代码

一如既往…

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseList(ListNode head) { int count = 0; ListNode a = head; if(a == null){ return null; } if(a.next == null){ return a; } while(a.next!=null){ count ++; a = a.next; } int time = 0; int len = count; ListNode header = new ListNode(0); ListNode shitty = header; while(count!=-1){ a = head; shitty.next = getLastNode(count,a); shitty = shitty.next; count--; } return header.next; } public static ListNode getLastNode(int count,ListNode a){ int i =0; while(a!=null&&i<count){ a =a.next; i++; } return new ListNode(a.val); } }

定义了许多乱七八糟的东西hhh，还是一如既往的烂

三、题解

法1、双指针迭代

申请两个指针一个叫curr，指向head，一个叫pre，目前是空

把curr的next先拿到，叫tmp把让curr.next指向 prepre = curr ，curr = tmp；重复以上步骤，直到curr为空

代码：

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseList(ListNode head) { ListNode curr = head; ListNode pre = null; ListNode tmp = null; while(curr!=null){ tmp = curr.next; curr.next = pre; pre = curr; curr = tmp; } return pre; } }

法2、递归

这个方法比较难理解，各位可以根据大神的讲解一起查看

https://leetcode-cn.com/problems/reverse-linked-list/solution/dong-hua-yan-shi-206-fan-zhuan-lian-biao-by-user74/

class Solution { public ListNode reverseList(ListNode head) { //递归终止条件是当前为空，或者下一个节点为空 if(head==null || head.next==null) { return head; } //这里的cur就是最后一个节点 ListNode cur = reverseList(head.next); //这里请配合动画演示理解 //如果链表是 1->2->3->4->5，那么此时的cur就是5 //而head是4，head的下一个是5，下下一个是空 //所以head.next.next 就是5->4 head.next.next = head; //防止链表循环，需要将head.next设置为空 head.next = null; //每层递归函数都返回cur，也就是最后一个节点 return cur; } }