题解 | #反转链表#遍历/栈/前驱插入/递归

解法1:从头到尾挨个反转节点

注意点是：

• 防止链表成环，所以inverse之前要先head.next = null;
• 一定要保存三个节点：当前节点，前一个节点和下一个节点
• 因为要反转当前节点和前一个节点之间的指向
• inverse之前也要保存下一个节点，否则inverse之后该节点地址会丢失

public class Solution {
    public ListNode ReverseList(ListNode head) {
        if (head == null) {
            return head;
        }
		//keep 3 node to track
        ListNode current = head.next;
        ListNode prevNode = head;
        ListNode nextNode = null;
	   //delete pointer to invoid circle  
        head.next = null;
        while (current != null) {
		  // save next node before inverse
            nextNode = current.next;
		  //inverse
            current.next = prevNode;
		  // move pointer after inverse
            prevNode = current;
            current = nextNode;
        }
        return prevNode;
    }
}

时间复杂度：O(n)

空间复杂度：O(1)

解法2:借助栈

import java.util.*;
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        Stack<ListNode> backup = new Stack<ListNode>();
        ListNode current = head;
        while (current != null) {
            backup.push(current);
            current = current.next;
        }

        ListNode newHead = backup.pop();
        current = newHead;
        ListNode next;
        while (!backup.empty()) {
            next = backup.pop();
            current.next = next;
            next.next = null;
            current = next;
        }
        return newHead;
    }
}

时间复杂度O(n), 空间复杂度O(n)

解法3:新建链表法/前驱插入

public class Solution {
    public ListNode ReverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = null;
        ListNode current = head;
        ListNode next;
        while (current != null) {
            next = current.next;
            current.next = newHead;
            newHead = current;
            current = next;    
        }
        return newHead;
    }
}

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

解法4:递归

public class Solution {
    public ListNode ReverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode reverseOfNext = ReverseList(head.next);
        head.next.next = head;
        head.next = null;
        return reverseOfNext;
    }
}

终止条件是，当只存在一个节点或者链表为空的时候

操作：

1.先对下一个节点的列表进行反转此时可以拿到反转后链表的头节点

2.head 此时作为最后一个需要反转的节点，也进行一个反转操作，head 要指向null，否则会出现循环

3.返回的节点是reverseOfNext, 相当于遍历到终止条件的时候得到的节点就是一个反转后链表的头节点，所有ReverseList方法返回的节点都是同一个它，但是更重要的是这个方法进行的反转操作