206 Reverse Linked List

Reverse a singly linked list.

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

• iterative

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

    }
}

• recursive to reverse a linked list recursively, we need to keep track of two nodes, the recursive function should return new head, and before jump into the recursive function, we need keep track of the tail of new list.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        //get new tail.
        ListNode tail = head.next;
        //remove old head.
        head.next = null;
        ListNode newHead = reverseList(tail);
        tail.next = head;

        return newHead;
    }