重排序链表

143. 重排链表

难度中等567

给定一个单链表 L：L0→L1→…→L**n-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→L**n-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1:

给定链表 1->2->3->4, 重新排列为 1->4->2->3.

示例 2:

给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

通过次数91,252

提交次数151,832

请问您在哪类招聘中遇到此题？

找中点，翻转，一一链接

public class Solution {
    public void reorderList(ListNode head) {
        if(head==null)return;
        ListNode fast = head;
        ListNode slow = head;
        // 找中点
        int cnt = 0;
        while(fast!=null){
            fast = fast.next;
            cnt++;
            if(fast!=null) fast = fast.next;
            slow = slow.next;
        }
        if(slow==null)return;
        // 链表反转
        ListNode pre = null;
        ListNode cur = slow;
        
        while(cur!=null){
            ListNode nex = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nex;
        }
        ListNode temp = head;
        cur = head.next;
        // 开始链接
        for(int i=1;i<cnt*2;i++){
            if(i%2==1){
                temp.next = pre;
                if(pre==null)continue;
                pre = pre.next;
            }else{
                temp.next = cur;
                if(cur==null)continue;
                cur = cur.next;
            }
            temp = temp.next;
            if(temp==null)break;
        }

    }
}

找中点，翻转后面，然后一一链接

• 快慢指针找中点
• 翻转后面的节点
• 奇数的时候把后面链表的元素链接到链表上，偶数的时候把前面链表的元素链接到链表上

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        // 或得中间的那个节点并且计算链表的长度
        int count = 0 ;
        while(fast!=null){
            fast = fast.next;
            count++;
            if(fast!=null){
                fast = fast.next;
                count++;
            }
            slow = slow.next;
        }
        // 后面链表的第一个节点是slow
        ListNode headAfter = slow;

        // 翻转链表
        ListNode dNode = new ListNode(0);
        dNode.next = headAfter;
        while(headAfter!=null){
            ListNode nex =headAfter.next;
            if(nex!=null){
                headAfter.next = nex.next;
                nex.next = dNode.next;
                dNode.next = nex;
            }else{
                // 一定不要忘了break,否则最后一个节点无法处理
                break;
            }
        }
        // 得到翻转后的链表
        slow = dNode.next;

        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;
        ListNode cur = head;
        ListNode HeadBefore = head.next;
        for(int i=1;i<count;i++){
            if(i%2==1){
                cur.next = slow;
                slow = slow.next;
            }else{
                cur.next = HeadBefore;
                HeadBefore=HeadBefore.next;
            }
            cur = cur.next;
        }
        // 防止出现环路
        cur.next = null;
        
        head = dummyNode.next;
    }
}

赏

谢谢你请我吃糖果

微信