算法系列-力扣206-单链表反转

题目说明

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

方法一：头插法反转链表

思路：

1. 声明p指针指向原头节点，并将头节点置空；
2. p指针循环原链表将元素用头节点插入法逐个插入head中；（head为反转后链表头）
3. 整个循环完毕，我们就能得到反转后的链表了，存储在head中。
   head = A -> B -> C -> D -> null
   p = head ; head = null;
   head = null ;
   A插入head p.next = head.next; head = p;
   head = A -> null
   B插入head
   head = B -> A -> null
   C插入head
   head = C -> B -> A -> null
   D插入head
   head = D -> C -> B -> A -> null
   整个反转完成

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

算法分析

时间复杂度为O(n)
空间复杂度为O(1)

方法二：双指针局部反转

     * head = 1 -> 2 -> 3 -> 4 -> null* null <- 1  2 -> 3 -> 4 -> null* null <- 1 <- 2  3 -> 4 -> null* null <- 1 <- 2 <- 3  4 -> null* null <- 1 <- 2 <- 3 <- 4  = head

思路：
1.声明cur和next两个指针，用cur指针指向当前需要处理节点，next指向cur下一个节点
2.cur起点为null，next起点为头节点
3.将next的后续节点指向cur这样就把next和原链表分离开来了，next和cur分别前进一步
4.继续3，直到next为null，cur就是反转后链表的头结点

` 思考1：为什么cur要从null开始，从第一个节点开始可以吗？为什么？

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseList(ListNode head) {/*** head = 1 -> 2 -> 3 -> 4 -> 5 -> null * null <- 1  2 -> 3 -> 4 -> 5 -> null * null <- 1 <- 2  3 -> 4 -> 5 -> null * ...* null <- 1 <- 2  <- 3  <- 4  <- 5 = head* 1.用cur指针指向当前需要处理节点，next指向cur下一个节点* 2.将cur next进行局部反转* 3.cur和next前进一步继续2直到next指向链尾*/ListNode cur=null;ListNode next=head;ListNode tmp=null;while(next!=null){tmp = next.next;next.next=cur;// 前进一步cur=next;next=tmp;            }return cur;}
}

方法三：递归反转

解题思路：
1.递归到最后一个节点作为表头节点即为revHead
2.在递归函数逐步返回的过程中将当前节点的后续节点指向当前节点
3.再当前节点后续节点置空，和原有链表分离，对于反转前链表的非头节点来讲不是必须的，为了简单统一处理
4.完成2-3步就完成一次局部反转，直到第一个调用处理完毕就得到反转后的链表

如下过程所示：
head = 1 -> 2 -> 3 -> 4 -> 5 -> null
head = 1 -> 2 -> 3 -> 4 -> 5 = revHead
head = 1 -> 2 -> 3 -> 4 null <- 4 <- 5 = revHead
head = 1 -> 2 -> 3 null <- 3 <- 4 <- 5 = revHead
head = 1 -> 2 -> 3 null <- 2 <- 3 <- 4 <- 5 = revHead
head = 1 -> null ， null <- 1 <- 2 <- 3 <- 4 <- 5 = revHead
revHead = 5 -> 4 -> 3 -> 2 -> 1 -> null

递推公式：
node.next.next = node
node.next = null

终止条件：
node.next == null

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseList(ListNode head) {/*** 1.递归到最后一个节点作为表头节点即为revHead* 2.在递归函数逐步返回的过程中将当前节点的后续节点指向当前节点* 3.再当前节点后续节点置空，和原有链表分离，对于反转前链表的非头节点来讲不是必须的，为了简单统一处理* 4.完成2-3步就完成一次局部反转，直到第一个调用处理完毕就得到反转后的链表*                            revHead* head = 1 -> 2 -> 3 -> 4 -> 5 -> null* head = 1 -> 2 -> 3 -> 4 -> 5 = revHead* head = 1 -> 2 -> 3 -> 4  null <- 4 <- 5 = revHead* head = 1 -> 2 -> 3  null <- 3 <- 4 <- 5 = revHead* head = 1 -> 2 -> 3 null <- 2 <- 3 <- 4 <- 5 = revHead* head = 1 -> null ， null <- 1 <- 2 <- 3 <- 4 <- 5 = revHead* revHead = 5 -> 4 -> 3 -> 2 -> 1 -> null*/// 空判定if(head == null){return null;}// 递归终止条件：递归到最后一个节点时返回作为反转后链表的头结点if(head.next == null){return head;}ListNode revHead = reverseList(head.next);// 倒数第二个节点开始，对示例而言节点4才会进入到下面的逻辑head.next.next = head;head.next = null;return revHead;}
}

算法分析：
时间复杂度O(n)
空间复杂度O(n)

思考

思考1：为什么cur要从null开始，从第一个节点开始可以吗？为什么？

cur不一定非得初始为null也可以从第一个节点开始，只不过要额外处理一下头结点的逻辑，即第一个节点的时候需要把cur的后继节点置为空，
并且next的后续节点置为cur，
这样后续的操作就是一样的了。

    public ListNode reverseList(ListNode head) {ListNode cur=head;ListNode next=head.next;cur.next=null;ListNode tmp=null;while(next!=null){tmp = next.next;next.next=cur;// 前进一步cur=next;next=tmp;}return cur;}