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

Amazon

  • Method 1: loop ```Java /**
    • 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, cur = head, next = null; while(cur != null){ next = cur.next; cur.next = pre; pre = cur; cur = next; } return pre; } } ```

    • Method 2: Recursion ```Java /**
      • Definition for singly-linked list.
      • public class ListNode {
      • int val;
      • ListNode next;
      • ListNode(int x) { val = x; }
      • } */ class Solution { private ListNode res; public ListNode reverseList(ListNode head) { if(head == null) return head; reverse(head); head.next = null; return res; } private ListNode reverse(ListNode node){ if(node.next == null){ this.res = node; return node; } ListNode next = reverse(node.next); next.next = node; return node; } } ```