原题
反转一个单链表。
示例：
输入： 1->2->3->4->5->NULL
输出： 5->4->3->2->1->NULL
进阶：
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
解法
思想
- 迭代（两种解法）
- 双指针
- 旋转前半部分
cur其实就是head
- 双指针
- 递归
从最后一个节点开始回溯，将箭头倒置。
代码
迭代：
- 双指针(作者：王尼玛)
class Solution {
public ListNode reverseList(ListNode head) {
//申请节点，pre和 cur，pre指向null
ListNode pre = null;
ListNode cur = head;
ListNode tmp = null;
while(cur!=null) {
//记录当前节点的下一个节点
tmp = cur.next;
//然后将当前节点指向pre
cur.next = pre;
//pre和cur节点都前进一位
pre = cur;
cur = tmp;
}
return pre;
}
}
- 旋转前半部分
/**
* 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 newHead = head;
ListNode cur = head;
if(head == null) return null;
while(cur.next != null){
//记录不动的节点
ListNode follow = cur.next.next;
//前半部分连成环
cur.next.next = newHead;
newHead = cur.next;
//将cur连到后半部分上
cur.next = follow;
}
return newHead;
}
}
递归：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
//从最后一个节点回溯
if(head==null||head.next==null){
return head;
}
ListNode node = reverseList(head.next);
//将head和head.next之间的箭头反转
head.next.next = head;
head.next = null;
return node;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode206-%e5%8f%8d%e8%bd%ac%e9%93%be%e8%a1%a8/
