Reverse Linked List

Reverse a singly linked list.

click to show more hints.

Hint:

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

==

/**

 * 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;

        }    

        ListNode p = head;

        ListNode prev = null;

        while (p != null) {

            ListNode nextP = p.next;

            

            p.next = prev;

            

            prev = p;

            p = nextP;

        }

        return prev;

    }

}

=======

/**

 * 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;

        }

        ListNode next = head.next;

        head.next = null;

        

        ListNode newHead = reverseList(next);

        next.next = head;

        

        return newHead; 

    }

}