首页 > 试题广场 >

重排链表

[编程题]重排链表
  • 热度指数：129965 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
将给定的单链表：
重新排序为：
要求使用原地算法，不能只改变节点内部的值，需要对实际的节点进行交换。

数据范围：链表长度 ，链表中每个节点的值满足

要求：空间复杂度 并在链表上进行操作而不新建链表，时间复杂度
进阶：空间复杂度 ， 时间复杂度
示例1

输入

{1,2,3,4}

输出

{1,4,2,3}

说明

给定head链表1->2->3->4, 重新排列为 1->4->2->3,会取head链表里面的值打印输出 1
示例2

输入

{1,2,3,4,5}

输出

{1,5,2,4,3}

说明

给定head链表1->2->3->4->5, 重新排列为 1->5>2->4->3,会取head链表里面的值打印输出
示例3

输入

{}

输出

{}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息
算法知识视频讲解
添加回答
Javascript
fighting的小郑头像 fighting的小郑
function reorderList( head ) {
    // write code here
    if(!head) return
    let a=[]
    while(head){
        a.push(head)
        head=head.next
}
    let len=Math.floor(a.length/2)
    for(let j=0;j<len;j++){
        a[j].next=a[a.length-1-j]
        a[a.length-1-j].next=a[j+1]
}
        a[len].next=null
    return a[0]
}
module.exports = {
    reorderList : reorderList
};
发表于 2021-08-19 13:54:17 回复(0)
Javascript
Axton头像 Axton
在把每一个节点都加上 pre 后，形成双链表，可以从尾部开始往前遍历。类似双指针进行遍历即可。 
/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
 * 
 * @param head ListNode类 
 * @return void
 */
function reorderList( head ) {
  if (!head) {
    return head;
  }
  let cur = head;
  let pre = null;
  while (cur) {
    cur.pre = pre;
    pre = cur;
    cur = cur.next;
  }
  let tail = pre;
  cur = head;
  while (cur !== tail && cur.next !== tail) {
    let next = cur.next
    let pre = tail.pre;
    cur.next = tail;
    tail.next = next;
    cur = next;
    tail = pre;
  }
  tail.next = null;
  return head;
}
module.exports = {
    reorderList : reorderList
};


发表于 2021-08-02 10:58:07 回复(0)
JavaScript
splwany头像 splwany 
class Reorder {
    static splitList(head) {
        let slow = head, fast = head;
        while (fast && fast.next) {
            slow = slow.next;
            fast = fast.next.next;
        }
        let list1 = head;
        let list2 = slow.next;
        slow.next = null;
        return [list1, list2];
    }
    static reverseList(root) {
        let prev = null;
        while (root) {
            const next = root.next;
            root.next=  prev;
            prev = root;
            root = next;
        }
        return prev;
    }
    static insertMerge(list1, list2) {
        const head = list1;
        list2 = Reorder.reverseList(list2);
        while (list2) {
            const node = list2;
            list2 = list2.next;
            node.next = list1.next;
            list1.next = node;
            list1= node.next;
        }
        return head;
    }
}

/**
 * 
 * @param head ListNode类 
 * @return void
 */
function reorderList( head ) {
    if (!head || !head.next || !head.next.next) return head;
    const [list1, list2] = Reorder.splitList(head);
    return Reorder.insertMerge(list1, list2);
}

发表于 2021-04-20 18:13:20 回复(0)
JavaScript
别卷啦！头像 别卷啦！
定义fast为头部，slow为尾部
第一次遍历链表，是为了给每一个节点增加一个pre指针，指向上个节点，使其变成双向链表。以便slow节点从后向前遍历。
第二次遍历链表，fast通过next指针，slow通过pre指针，同时向中点靠拢，并把当前的slow节点插入到fast节点的next位置。
遍历完成，此时slow和fast节点可能重合，也可能一前一后。需要slow.next = null 作为收尾，中断与原有链表的连接，避免成环。
function reorderList( head ) {
    // write code here
  if (head === null || head.next === null) return head
  let slow = head
  let fast = head
  while (slow && slow.next) {
    slow.next.pre = slow //变成双向链表
    slow = slow.next
  } 
  while (slow !== fast && slow.pre !== fast) {
    let next = fast.next
    fast.next = slow
    slow = slow.pre
    fast.next.next = next
    fast = next
  }
  slow.next = null
  return head
}


发表于 2021-01-19 11:55:10 回复(0)
JavaScript
牛客73632096号头像 牛客73632096号
解题思路：因为不知道链表的长度，因此采用快慢指针先找到中间节点的位置，然后将中间节点之后的链表反序，再将两个链表合并
注意：1.特殊情况的判断，如果head=null或head.next==null
            2.指针的移动注意临界值的判断，不要溢出，导致空指针的出现 
/**
 * 
 * @param head ListNode类 
 * @return void
 */

        function reorderList( head ) {
        //思路，先找到链表的中间节点，然后将中间节点后续的节点逆序，然后将逆序的节点按要求插入前一半链表中
        //利用快慢指针找中间节点,slow后边的都需要反序
        if(head==null||head.next==null){
            return ;
        }
        var slow=head;
        var fast=head;
        while(fast.next!=null&&fast.next.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            // console.log(slow.val)
        }
        //反序
        var pre=null;
        var cur=slow.next;
        var last=cur.next;
        while(cur!=null){
            cur.next=pre;
            pre=cur;
            cur=last;
            if(last!=null){
                last=last.next;
            }
        }
        slow.next=null;
        //重新构建
        var p=head;
        var p0=p.next;
        var q=pre;
        var q0=q.next;
        while(q!=null){
            p.next=q;
            q.next=p0;
            p=p0;
            if(p0!=null){
                p0=p0.next;
            }
            q=q0;
            if(q0!=null){
                q0=q0.next;
            }
        }
        p=head;
        while(p!=null){
            console.log(p.val);
            p=p.next;
        }
        return head;
    }
module.exports = {
    reorderList : reorderList
};


发表于 2020-08-21 20:10:22 回复(0)
提交观点

问题信息

链表
难度：
6条回答 44547浏览

热门推荐

通过挑战的用户

相关试题

重排链表

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号