Leetcode_206_Reverse Linked List

[lihe]

Reverse Linked List

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

算法思路：可以利用栈来实现；也可以利用迭代来实现。

class Solution {  // 栈
    public ListNode reverseList(ListNode head) {
        if(head == null) return null;
        Stack<ListNode> stack = new Stack<>();
        while(head != null){
            stack.push(head);
            head = head.next;
        }
        
        ListNode newHead = stack.pop();
        head = newHead;
        while (!stack.empty()){
            newHead.next = stack.pop();
            newHead = newHead.next;
        }
        newHead.next = null;
        return head;
    }
}

class Solution { // 迭代
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null){
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
}