Question

Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

Example:

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->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 reverseBetween(ListNode head, int m, int n) {
        int count = 0;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = dummy;
        ListNode mNode = null;
        while(cur.next != null && count < m - 1){
            count++;
            cur = cur.next;
        }
        mNode = cur;
        List<ListNode> result = new ArrayList<>();
        ListNode end = recursive(mNode.next, m, n, result);
        mNode.next = result.get(0);
        end.next = result.get(1);
        return dummy.next;
    }
    private static ListNode recursive(ListNode head, int count, int n, List<ListNode> result){
        if(count == n){
            result.add(head);
            result.add(head.next);
            return head;
        }else{
            count++;
            ListNode next = recursive(head.next, count, n, result);
            next.next = head;
            return head;
        }
    }
}

二刷

还是参考了一刷时候的结果。这道题在此处标记，过段时间还是要再刷一遍。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = dummy;
        int count = 0;
        while(cur.next != null && count++ < m - 1){
            cur = cur.next;
        }
        List<ListNode> temp = new LinkedList<>();
        ListNode end = reverse(cur.next, m, n, temp);
        cur.next = temp.get(0);
        end.next = temp.get(1);
        return dummy.next;
    }
    private ListNode reverse(ListNode head, int count, int n, List<ListNode> temp){
        if(count == n){
            temp.add(head);
            temp.add(head.next);
        }else{
            ListNode next = reverse(head.next, count + 1, n, temp);
            next.next = head;
        }
        return head;
    }
}