leetcode [#92]

目录

• 1. 题目
• 2. 解决方案
• 3. 注意事项

题目

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

Example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.

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

---

解决方案

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if(head == null) return null;
        int tempA = -1;
        ListNode pre = null;
        ListNode begin = null;
        ListNode end = null;
        ListNode before = null;

        ListNode fakeHead = new ListNode(0);
        fakeHead.next = head;
        ListNode p = fakeHead;

        while(p != null){
            tempA++;
            if(tempA < m-1){
                p = p.next;
            }
            if((tempA+1) == m) {
                pre = p;
                before = p;
                p = p.next;
            }
            if(tempA == m) {
                begin = p;
            }
            if(m <= tempA && tempA <= n){
                ListNode next = p.next;
                p.next = pre;
                pre = p;
                if(tempA == n){
                    end = p;
                }
                p = next;
            }
            if(tempA == n){
                begin.next = p;

                if(before != null){
                    before.next = end;
                }
                break;
            }
        }
        return fakeHead.next;
    }
}

---

注意事项

1. 使用“头指针”，从而去除头结点的特殊性。
2. 难度在于要只一遍遍历且原地完成。
3. 记录要翻转节点的前一个节点、要翻转的第一个节点、要翻转的最后一个节点。
4. 核心代码：

   if(m <= tempA && tempA <= n){
       ListNode next = p.next;
       p.next = pre;
       pre = p;
       if(tempA == n){
           end = p;
       }
       p = next;
   }

是使用了链表翻转的典型做法。