首页 > 试题广场 >

按照左右半区的方式重新组合单链表

[编程题]按照左右半区的方式重新组合单链表
  • 热度指数：1886 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个单链表的头部节点 head，链表长度为 N，如果 N 是偶数，那么前 N / 2 个节点算作左半区，后 N / 2 个节点算作右半区；如果 N 为奇数，那么前 N / 2 个节点算作左半区，后 N / 2 + 1个节点算作右半区。左半区从左到右依次记为 L1->L2->...，右半区从左到右依次记为 R1->R2->...，请将单链表调整成 L1->R1->L2->R2->... 的形式。

输入描述:
单链表的头节点 head。


输出描述:
在给定的函数内返回链表的头指针。
示例1

输入

6
1 2 3 4 5 6

输出

1 4 2 5 3 6

备注:
保证链表的长度不大于1000000
算法知识视频讲解
添加回答
Java
myorange头像 myorange
既然牛客只给了数组，又想让咱练习链表和树的题。那么咱就要有一套输入输出的模板，让思路聚焦在如何解题上。分享下我读入链表和输出链表的模板和使用样例。 
class Node {
    int val;
    Node next;

    Node(int val) {
        this.val = val;
    }
}

    /*

    private static Node input(Scanner sc, int n) {
        Node head = null, p = null;
        while(n-- > 0) {
            if (head == null) {
                head = p = new Node(sc.nextInt());
            } else {
                p.next = new Node(sc.nextInt());
                p = p.next;
            }
        }
        return head;
    }

    private static void output(Node head) {
        Node p = head;
        StringBuilder cache = new StringBuilder();
        while(p != null) {
            cache.append(p.val).append(" ");
            p = p.next;
        }
        if (cache.length() > 0) {
            cache.deleteCharAt(cache.length() - 1);
        }
        System.out.println(cache);
    }
     */
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Node head = input(sc, n);
        head = merge(head);
        output(head);
    }

    static Node merge(Node head) {
        if (head == null || head.next == null) return head;
        Node fast = head, slow = head;
        Node pre = null;
        while(fast != null) {
            fast = fast.next;
            if (fast != null) {
                fast = fast.next;
                pre = slow;
                slow = slow.next;
            }
        }
        if (pre != null) {
            pre.next = null;
        }
        Node p = head, q = slow, next = null;
        while(p != null) {
            pre = q;
            next = q.next;
            q.next = p.next;
            p.next = q;
            p = q.next;
            q = next;
        }
        pre.next = q;
        return head;
    }

    private static Node input(Scanner sc, int n) {
        Node head = null, p = null;
        while(n-- > 0) {
            if (head == null) {
                head = p = new Node(sc.nextInt());
            } else {
                p.next = new Node(sc.nextInt());
                p = p.next;
            }
        }
        return head;
    }

    private static void output(Node head) {
        Node p = head;
        StringBuilder cache = new StringBuilder();
        while(p != null) {
            cache.append(p.val).append(" ");
            p = p.next;
        }
        if (cache.length() > 0) {
            cache.deleteCharAt(cache.length() - 1);
        }
        System.out.println(cache);
    }

}



发表于 2021-08-14 20:34:00 回复(0)
提交观点

问题信息

链表
上传者：小小
难度：
1条回答 2609浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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