206. Reverse Linked List

题目

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

示例1:

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例2：

输入：head = [1,2]
输出：[2,1]

示例3：

输入：head = []
输出：[]

提示：

• 链表中节点的数目范围是 [0, 5000]
• -5000 <= Node.val <= 5000

进阶

链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

解法

解法一：

递归

JAVA

public ListNode reverseList(ListNode head) {
        return reverse(null, head);
    }
	
	private ListNode reverse(ListNode next, ListNode current) {
		if (null == current) {
			return next;
		}
		
		ListNode nextNode = current.next;
		current.next = next;
		return reverse(current, nextNode);
	}

解法二：

迭代

借助栈，遍历链表，将每个元素入栈。

再次从头遍历链表，它们的值用栈中的元素覆盖即可。

JAVA

public ListNode reverseList(ListNode head) {
        Stack<Integer> values = new Stack<>();
        ListNode p = head;
        while (null != p) {
        	values.add(p.val);
        	p = p.next;
        }
        
        p = head;
        while (null != p) {
        	p.val = values.pop();
        	p = p.next;
        }
        return head;
    }

解法三：

原地替换

Java

public ListNode reverseList(ListNode head) {
        ListNode last = null;
        ListNode current = head;
        if(head == null) return null;
        ListNode next = current.next;
        
        while(current != null){
            current.next = last;
            last = current;
            current = next;
            if(current != null)
                next = current.next;
        }
        
        return last;
        
    }