Lexi's Leetcode solutions

a->b->c->d->e => a->e->b->d->c，要求inplace，不能用额外空间（要不然直接reverse成另一个就好办了），不能直接改动list的值。

这题有点写长了，过一阵看看网上有没有好点的做法。O(n)。

算法：

1. 过一遍算出总长度len
2. 再过一遍找到中点或第二部分的第一个点(a->b->c->d->e和a->b->c->d的都是c）
3. reverse后半部分，变成a->b->c<-d<-e 或者 a->b->c<-d，最后中点c的next置空
4. 两头穿插合并，直到找到c这点。c肯定是一起找到（奇数）或者右半部分先找到（偶数）

public void reorderList(ListNode head) {
    if (head == null)
        return;
    ListNode p = head;
    int len = 0;
    while (p != null) {
        len++;
        p = p.next;
    }
    p = head;
    for (int k = 0; k < len / 2; k++) {
        p = p.next;
    } //p points to mid point
    ListNode curr = p.next, next;
    p.next = null;
    while (curr != null) { //开始reverse后半部分
        next = curr.next;
        curr.next = p;
        p = curr;
        curr = next;
    }//now p points to the last ele
    ListNode h = head;
    while (h.next != p && h != p) {
        ListNode tempH = h.next;
        ListNode tempP = p.next;
        h.next = p;
        p.next = tempH;
        h = tempH;
        p = tempP;
    }
}

原来反转单链表有另一种简洁的做法，看来每道题过了之后一定还得看别人答案才行，这才能做到“做的多了就会了”。

• 比如反转b->c->d：a->b->c->d->e => a->d->c->b->e
• 三个variable
  1. prevM：指向反转部分的前一个元素a
  2. prev：指向已经反转成功的最后一个元素，永远是prevM.next，不需要改动。
  3. curr：想往prevM后面塞的那个元素。
• 算法：每次拿出右边的新元素，往prevM后面插，最后curr==不需要反转的section的第一个节点时退出

public ListNode reverseBetween(ListNode head, int m, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode prevM = dummy, prev, curr;
    for (int i = 1; i <= n; i++) {
        if (i < m) {
            prevM = prevM.next;
        } else if (i == m) {
            prev = prevM.next;
            curr = prev.next;
        }else {
            prev.next = curr.next;
            curr.next = prevM.next;
            prevM.next = curr;
            curr = prev.next;
        }
    }
    return dummy.next;
}

看别人思路：这个既然要rotate，不如先连起来loop，这样怎么也不怕null pointer exception了。然后再找到该断开的地方断开。

public ListNode rotateRight(ListNode head, int n) {

    if (head == null || n == 0)
        return head;
    ListNode p = head;
    int len = 1;//since p is already point to head
    while (p.next != null) {
        len++;
        p = p.next;
    }
    p.next = head; //form a loop
    n = n % len;
    for (int i = 0; i < len - n; i++) { //len-n一画就出来了
        p = p.next;
    } //now p points to the prev of the new head
    head = p.next;
    p.next = null;
    return head;
}

keep 3个pointer：

• prevStart：要reverse的section的前一个节点
• start：section第一个
• end：section最后一个

然后就每次reverse好了section，和prevStart连上就行了，然后prevStart 越过k个，接着做。这是个练习linked list的好题。

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode prevStart = dummy;
    while (prevStart != null) {
        ListNode start = prevStart.next;
        ListNode end = prevStart;
        for (int i = 0; i < k; i++) {
            end = end.next;
            if (end == null)
                return dummy.next;
        }
        prevStart.next = reverse(start, end);
        for (int i = 0; i < k; i++) {
            prevStart = prevStart.next;
        }
    }
    return dummy.next;
}
private ListNode reverse(ListNode start, ListNode end) {
    ListNode prev = start;
    ListNode curr = start.next;// want to make curr point to prev
    ListNode afterEnd = end.next;
    while (curr != afterEnd) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    start.next = afterEnd;
    return end;
}