题目
给单链表的头节点 head ，请反转链表，并返回反转后的链表。
示例
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
|
方法一： 双指针迭代
思路
首先要引入两个指针，分别是prev和curr,因为要把链表反转，那么就必须对next做文章，通过curr指针让当前节点的next指向上一个节点，而上一个节点由prev指针来表示。指向更改后两个指针往后移位。
但是在这里有一个问题，就是当curr.next->prev后，如图，节点1和节点2之间就断开了，那么curr指针就无法进行后移操作，所以我们还需要一个临时变量next，在将curr.next->prev前，先将curr的下一个节点暂时保存在这个临时变量next中，等第一个节点反转之后，prev后移，再将next里的值给到curr实现其后移。
代码实现
public class test {
public static void main(String[] args) {
Node head = new Node(0);
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
head.setNext(node1);
node1.setNext(node2);
node2.setNext(node3);
node3.setNext(node4);
node4.setNext(node5);
Node h = head;
while (h != null) {
System.out.print(h.getData() + " ");
h = h.getNext();
}
Solution solution = new Solution();
head = solution.reverse(head);
System.out.println("\n**************************");
while (null != head) {
System.out.print(head.getData() + " ");
head = head.getNext();
}
}
}
class Solution{
public Node reverse(Node head) {
if (head == null) {
return head;
}
Node prev = null;
Node curr = head;
Node temp;
while (curr != null) {
temp = curr.getNext();
curr.setNext(prev);
prev = curr;
curr = temp;
}
return prev;
}
}
class Node{
private int Data;
private Node next;
public Node(int Data){
this.Data = Data;
}
public int getData(){
return Data;
}
public void setData(int Data){
this.Data = Data;
}
public Node getNext(){
return next;
}
public void setNext(Node next){
this.next = next;
}
}
|
输出结果：
0 1 2 3 4 5
5 4 3 2 1 0
算法主体
Java
class Solution{
public Node reverse(Node head) {
if (head == null) {
return head;
}
Node prev = null;
Node curr = head;
Node temp;
while (curr != null) {
temp = curr.getNext();
curr.setNext(prev);
prev = curr;
curr = temp;
}
return prev;
}
}
|
C
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode* prev = NULL;
struct ListNode* curr = head;
while (curr) {
struct ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
|
复杂度
时间复杂度：O(N)，N是链表长度，因为需要遍历链表一次
空间复杂度：O(1)
方法二：递归
思路
通过不断调用函数递归，在归的过程中将节点指向反向，这里用head.next.next = head;
往上的过程中，子节点已经反转好，让自己和子节点进行反转即可
递归结束的条件，当前链表为空或者链表里只有一个节点(因为此时不需要反转)
代码实现
public class test {
public static void main(String[] args) {
Node head = new Node(0);
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
head.setNext(node1);
node1.setNext(node2);
node2.setNext(node3);
node3.setNext(node4);
node4.setNext(node5);
Node h = head;
while (h != null) {
System.out.print(h.getData() + " ");
h = h.getNext();
}
Solution solution = new Solution();
head = solution.reverse1(head);
System.out.println("\n**************************");
while (null != head) {
System.out.print(head.getData() + " ");
head = head.getNext();
}
}
}
class Solution{
public Node reverse1(Node head) {
if(head == null || head.getNext() == null){
return head;
}
Node newHead = reverse1(head.getNext());
head.getNext().setNext(head);
head.setNext(null);
return newHead;
}
}
class Node{
private int Data;
private Node next;
public Node(int Data){
this.Data = Data;
}
public int getData(){
return Data;
}
public void setData(int Data){
this.Data = Data;
}
public Node getNext(){
return next;
}
public void setNext(Node next){
this.next = next;
}
}
|
算法主体
Java
class Solution{
public Node reverse1(Node head) {
if(head == null || head.getNext() == null){
return head;
}
Node newHead = reverse1(head.getNext());
head.getNext().setNext(head);
head.setNext(null);
return newHead;
}
}
|
递归算法不太好理解，可以认为是大问题一步步分解成小问题，再返回上一级问题执行同样的操作，一步步还回去。这类问题分清楚递和归的过程。
C
struct ListNode* reverseList(struct ListNode* head) {
if (head == NULL || head->next == NULL) {
return head;
}
struct ListNode* newHead = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return newHead;
}
|
复杂度
时间复杂度：O(N)，假设 N 是列表的长度，那么时间复杂度为 O(N)。
空间复杂度：O(N)，由于使用递归，将会使用隐式栈空间。递归深度可能会达到 N 层。
