题目

给定一个链表，按照每k个逆序，不够k个的正常顺序，
例如：
input: 链表[1->2->3->4->5->6->7], k=2
out: 链表[2->1->4->3->6->5->7]

思路

1. 按照每段（k个）来遍历，通过每段的pre、head、tail指针来实现
2. 逆转每段链表
3. 然后将子链表接回原链表

实现

    private ListNode reserve(ListNode head, int k){
        //1.创建一个虚拟头节点，用来方便链接每段的头部
        ListNode dupHead = new ListNode(-1);
        dupHead.next = head;
        //2.每段头部的上一个指针，第一段头部的指针为dupHead
        ListNode pre = dupHead;
        //3.while按照每段进行循环，通过head = tail.next来实现
        while (head!=null){
            //4. 每段的尾就是刚开始都是每段的头的上一个节点，然后数k步得到的
            ListNode tail = pre;
            for (int i = 0; i < k; i++) {
                tail = tail.next;
                //如果不够k，那么直接返回即可
                if(tail == null){
                    return dupHead.next;
                }
            }
            //临时变量，用来记录下一段的head，逆转该段后需要链接上
            ListNode next = tail.next;
            //5.逆转子链表
            ListNode[] listNodes = myReserve(head, tail);
            head = listNodes[0];
            tail = listNodes[1];
            //6.子链表重新接回到原链表
            pre.next = head;
            tail.next = next;
            pre = tail;
            head = tail.next;
        }
        return dupHead.next;
    }

    public ListNode[] myReserve(ListNode head, ListNode tail){
        ListNode preNode = head;
        ListNode curNode = head;
        ListNode copyNode = null;
        while (curNode!=tail){
            preNode = copyNode;
            copyNode = curNode;
            curNode = copyNode.next;
            copyNode.next = preNode;
        }
        curNode.next = copyNode;
        return new ListNode[]{curNode, head};
    }

分析：上诉解法的时间复杂度O(n), 但是在myReserve new了(n/k)*2 的内存，所以空间复杂度也是O(n)

将空间复杂度优化为O(1),如下：

    private ListNode reserve1(ListNode head, int k){
        //1.创建一个虚拟头节点，用来方便链接每段的头部
        ListNode dupHead = new ListNode(-1);
        dupHead.next = head;
        //2.每段头部的上一个指针，第一段头部的指针为dupHead
        ListNode pre = dupHead;
        //3.while按照每段进行循环，通过head = tail.next来实现
        while (head!=null){
            //4. 每段的尾就是刚开始都是每段的头的上一个节点，然后数k步得到的
            ListNode tail = pre;
            for (int i = 0; i < k; i++) {
                tail = tail.next;
                //如果不够k，那么直接返回即可
                if(tail == null){
                    return dupHead.next;
                }
            }
            //临时变量，用来记录下一段的head，逆转该段后需要链接上
            ListNode next = tail.next;


            //5.逆转子链表
            ListNode tmpHead = head;
            ListNode preNode = tmpHead;
            ListNode curNode = tmpHead;
            ListNode copyNode = null;
            while (curNode!=tail){
                preNode = copyNode;
                copyNode = curNode;
                curNode = copyNode.next;
                copyNode.next = preNode;
            }
            curNode.next = copyNode;
            head =  curNode;
            tail = tmpHead;

            //6.子链表重新接回到原链表
            pre.next = head;
            tail.next = next;
            pre = tail;
            head = tail.next;
        }
        return dupHead.next;
    }

• ← Previous Post
• Next Post →