leetcode: Reverse Linked List II

问题描述：

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

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

原问题链接：https://leetcode.com/problems/reverse-linked-list-ii/

 

问题分析

　　这个问题是反转单链表问题的一个稍微的变化，在之前的文章里也有讨论过。我们有了前面反转链表的基础再来看这个问题的话，基本的思路如下。

　　首先需要找到第n个元素所在的位置，然后再找到第m个元素所在的位置。因为我们这里反转元素的时候是从第m个开始的，需要一个指向m的前一个元素的引用。这样在后面的调整中才能保证前面的引用能够反转过来。为了得到这个之前一个的节点，我们需要定义一个临时节点dummy，它的next指向head。这样它往前移动m步就正好指向第m个元素的前一个。

　　后面在反转完链表之后还有一个细节就是我们这里要记录这里开始和结束节点它们所指向的下一个元素的位置。所以需要额外定义变量prev来保存。关于这些引用调整的细节比较繁琐，在详细实现之前最好画图先详细分析一下。这里就不再画图赘述了。

　　详细的代码实现如下：

 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if(m == n) return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode start = findNode(head, m);
        ListNode prev = findNode(dummy, m);
        ListNode end = findNode(head, n);
        if(start == null || end == null || prev == null) return head;
        ListNode pre = null, temp;
        while(start != end) {
            temp = start;
            start = start.next;
            temp.next = pre;
            pre = temp;
        }
        temp = start.next;
        start.next = pre;
        prev.next.next = temp;
        prev.next = start;
        return dummy.next;
    }
    
    private ListNode findNode(ListNode head, int n) {
        while(head != null && n - 1 > 0) {
            head = head.next;
            n--;
        }
        return head;
    }
}