Reverse Linked List

Source

• leetcode: Reverse Linked List

Reverse a singly linked list.

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

Java

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


    //第二种方法
    // public ListNode reverseList(ListNode head){
    //     ListNode pre = new ListNode(0);
    //     pre.next=head;
    //     ListNode cur =head;
    //     while(cur!=null && cur.next!=null){
    //         ListNode tmp = cur.next.next;
    //         cur.next.next = pre.next;
    //         pre.next = cur.next;
    //         cur.next = tmp;
    //     }
    //     return pre.next;
    // }


    //recursive 
    public ListNode reverseList(ListNode head) {
        if(head==null || head.next==null)
            return head;
        ListNode nextNode=head.next;
        ListNode newHead=reverseList(nextNode);
        nextNode.next=head;
        head.next=null;
        return newHead;
    }
}