reverse-part-linked-list

"翻转部分链表"

Posted by shihunyewu on January 19, 2019

链表就地转置之定点部分转置

92. Reverse Linked List II

边界值值得思考

大神版本

/**
 * 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) {
        if (head == null) return null;
        ListNode newHead = new ListNode(0);
        newHead.next = head;
        ListNode pre = newHead;
        
        for (int i = 0; i < m-1; i++) pre = pre.next;
        
        ListNode start = pre.next;
        ListNode after = start.next;
        
        for (int i = 0; i < n-m; i++) {
            start.next = after.next;
            after.next = pre.next;
            pre.next = after;
            after = start.next;
        }
        
        return newHead.next;
    }
}

我的版本

/**
 * 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 p0 = head;
        ListNode pre = new ListNode(0);
        pre.next = head;
        ListNode p1 = head.next;
        if(p1 == null)
            return head;
        
        int i = 0;
        for(i = 0; i < m - 1; i++){
            pre = pre.next;
            p0 = p0.next;
        }
        
        ListNode tmpHead = p0;
        p1 = p0.next;
        
        while(i++ < n - 1){
            tmpHead.next = p1.next;
            p1.next = p0;
            p0 = p1;
            p1 = tmpHead.next;
        }
        
        if(pre.next != head){
            pre.next = p0;
            return head;
        }else
            return p0;
        
    }
}

25. Reverse Nodes in k-Group 分组转置

迭代调用上面的操作即可,将每一段转置之后连接到新的链表上,这是主要思路。这个题目测试用例的一个细节的就是如果是剩余的节点数不足 k,不转置,这一点需要注意一下。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    ListNode h = new ListNode(0);
    ListNode c;
    int count = 0;
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode p = head;
        while(p != null){
            count++;
            p = p.next;
        }
        ListNode ret = sub(head, k);
        ListNode pre = ret;
        while(this.c != null){  // 终止条件判断
            while(pre.next != null){
                // System.out.println(pre.val);
                pre = pre.next;
            }
            ListNode tmp = sub(this.c, k);
            pre.next = tmp;
            pre = tmp;
        }
        return ret;
    }

    ListNode sub(ListNode head, int k){
        h.next = null;
        ListNode c = head;
        ListNode n = head;

        if(count - k < 0){
            this.c = null;   // 至关重要的终止条件
            return head;
        }
        else
            count -= k;

        for(int i = 0; i < k; i++){
            if(n == null){
                break;
            }
            n = n.next;
            c.next = h.next;
            h.next = c;
            c = n;
        }
        this.c = c; // 至关重要的终止条件
        return h.next;
    }
}