206. Reverse Linked List.md

206. Reverse Linked List

Question

Reverse a singly linked list.

Example:

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

Thinking:

• Method 1:遍历

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

• Method 2: 递归

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null) return head;
        List<ListNode> result = new ArrayList<>();
        ListNode end = recursive(head, result);
        end.next = null;
        return result.get(0);
    }
    private static ListNode recursive(ListNode pre, List<ListNode> result){
        if(pre != null && pre.next == null){
            result.add(pre);
            return pre;
        }
        ListNode next = recursive(pre.next, result);
        next.next = pre;
        return pre;
    }
}

二刷

1. 使用迭代法。

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

2. 使用递归法。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    ListNode ret = null;
    public ListNode reverseList(ListNode head) {
        if(head == null) return head;
        ListNode tail = reverseNode(head);
        tail.next = null;
        return this.ret;
    }
    
    private ListNode reverseNode(ListNode node){
        if(node.next == null){
            this.ret = node;
            return node;
        }else{
            ListNode next = reverseNode(node.next);
            next.next = node;
            return node;
        }
    }
}

Third Time

• Method 1: Loop

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

• Method 2: recursion

   /**
    * Definition for singly-linked list.
    * public class ListNode {
    *     int val;
    *     ListNode next;
    *     ListNode(int x) { val = x; }
    * }
    */
   class Solution {
   	private ListNode head = null;
   	public ListNode reverseList(ListNode head) {
   		if(head == null) return head;
   		getNext(null, head);
   		return this.head;
   	}
   	private void getNext(ListNode pre, ListNode cur){
   		ListNode next = cur.next;
   		if(cur.next == null){
   			this.head = cur;
   			cur.next = pre;
   			return;
   		}
   		cur.next = pre;
   		getNext(cur, next);
   	}
   }