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

1、思路

• 找到单链表中点，将单链表分成两段；

• 两条链表交叉合成一条新链表。

2、代码

list_node * findMid(list_node * head)   //取得单链表的中间节点，并保证后半部分长度大于等于前半部分
{
    auto fast = head->next, slow = head;

    while (fast->next != nullptr && fast->next->next != nullptr)
    {
        fast = fast->next->next;
        slow = slow->next;
    }

    return slow;
}

list_node * relocate(list_node * head)
{
    if (head == nullptr || head->next == nullptr) return head;

    auto mid = findMid(head);
    auto list1 = head, list2 = mid->next;
    mid->next = nullptr;        //断尾，切断list1尾部与list2头部的连接

    list_node *dummy = new list_node();
    auto *p = dummy;

    while (list1 != nullptr)    //list2的长度一定大于等于list1，故只需要判断list1即可
    {
        p = p->next = list1;    //交叉操作
        list1 = list1->next;

        p = p->next = list2;
        list2 = list2->next;
    }

    if (list2 != nullptr) p->next = list2;

    return dummy->next;
}

import java.util.Scanner;

public class Main {

    public static class Node {
        public int val;
        public Node next;
        Node() {}
        Node(int val, Node next) {
            this.val = val;
            this.next = next;
        }
    }

    public static Node reConstructList(Node head) {
        if (head == null || head.next == null) return head;
        Node p1 = head, p2 = head;
        while (p2.next != null && p2.next.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
        }
        p2 = p1.next;
        p1 = head.next;
        Node mid = p2;
        Node resHead = new Node();
        Node p3 = resHead;
        boolean flag = true;
        while (p1 != mid || p2 != null) {
            if (flag && p1 != mid) {
                p3.next = p1;
                p3 = p1;
                p1 = p1.next;
            } else {
                p3.next = p2;
                p3 = p2;
                p2 = p2.next;
            }
            flag = !flag;
        }
        return resHead;
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        Node head = new Node();
        Node p = head;
        for (int i = 0; i < n; i++) {
            int val = input.nextInt();
            Node node = new Node(val, null);
            p.next = node;
            p = node;
        }
        p = reConstructList(head).next;
        while (p != null) {
            System.out.print(p.val + " ");
            p = p.next;
        }
    }
}

n=int(input())
number_list=list(map(int,input().split()))
#分左右区
left_list=number_list[:n//2]
right_list=number_list[n//2:]
ans=[]
for i in range(len(left_list)):
    ans.append(left_list[i])
    ans.append(right_list[i])
#多了一个元素
if n%2!=0:
    ans.append(right_list[-1])
print(' '.join(map(str,ans)))

// 思路不是很难，难的就是指针的指向，有时候容易导致越界
# include <bits/stdc++.h>
using namespace std;

struct list_node{
    int val;
    struct list_node * next;
};


list_node * input_list(int* p)
{
    int n, val;
    list_node * phead = new list_node();
    list_node * cur_pnode = phead;
    scanf("%d", &n);
    *p = n;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &val);
        if (i == 1) {
            cur_pnode->val = val;
            cur_pnode->next = NULL;
        }
        else {
            list_node * new_pnode = new list_node();
            new_pnode->val = val;
            new_pnode->next = NULL;
            cur_pnode->next = new_pnode;
            cur_pnode = new_pnode;
        }
    }
    return phead;
}


list_node * relocate(list_node * head,int len)
{
    //////在下面完成代码
    if(head == nullptr || head->next == nullptr || head->next->next == nullptr){
        return head;
    }

    int temp = len/2;
    list_node * ans = head;
    list_node* p1 = head;
    list_node* p2 = head;
    list_node* p3 = p1->next;
    // 找到中间位置
    while(temp--){
        p2 = p2->next;
    }
    list_node* p5 = p2; // 后期作为判断循环退出条件
    list_node* p4 = p2->next;
    int time = len/2;
    while(time--){
        p1->next = p2;
        p1 = p3;
        p3 = p3->next;
        
        if(p1 == p5)break;
        if(p2->next != nullptr){
            p2 -> next = p1;
        }
        p2 = p4;
        if(p4 != nullptr){
            p4 = p4->next;
        }
    }
    return ans;

}


void print_list(list_node * head)
{
    while (head != NULL) {
        printf("%d ", head->val);
        head = head->next;
    }
    puts("");
}


int main ()
{   
    int len = 0;
    int* p = &len;
    list_node * head = input_list(p);
    list_node * new_head = relocate(head,len);
    print_list(new_head);
    return 0;
}

import java.io.*;

public class Main {
    static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine());
        Node h1 = new Node(-1);
        Node p = h1;
        String[] s1 = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            p.next = new Node(Integer.parseInt(s1[i]));
            p = p.next;
        }
        h1 = h1.next;//真实头结点

        Node h = solve(h1);
        while (h != null) {
            bw.write(h.val + " ");
            h = h.next;
        }
        bw.flush();
        bw.newLine();
    }

    private static Node solve(Node h) {
        Node hh = new Node(-1);//虚拟头结点
        Node p = hh;//游走指针
        Node l = h, r = h, pre = null;//pre是r的前驱
        int cnt = 1;//计数器，是奇数就连左半区
        for (int i = 0; i < n / 2; i++) {
            pre = r;
            r = r.next;
        }
        pre.next = null;//此时pre是左半区的尾节点
        while (l != null) {
            if (cnt % 2 == 1) {
                p.next = l;
                l = l.next;
            } else {
                p.next = r;
                r = r.next;
            }
            p = p.next;
            cnt++;
        }//还有右半区的最后1个或2个节点没处理
        //直接连起来即可
        if (r != null) pre.next = r;
        return hh.next;
    }
}
class Node {
    int val;
    Node next;

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

list_node * relocate(list_node * head)
{
    //////在下面完成代码
    list_node *l,*f,*temp;
    list_node *new_head = new list_node();
    list_node *cur = new_head;
    l = f = head;
    while(f->next && f->next->next){
        l = l->next;
        f = f->next->next;
    }
    f = head;
    if(n % 2 == 0) l = l->next;// 如果是偶数，l在中间左边，为了让在右边，向前进一个单位
    list_node *tag = l;
    int i = 1;
    //因为左半区插入先行，当f == tag，实际上与之对应的右半区第N/2个节点
    //还没有插入，所以加了个i的判断
    while(1){
        if(f == tag && i%2 == 1) break;
        if(i % 2 == 1){
            temp = f;
            f = f->next;
            temp->next = cur->next;
            cur->next = temp;
        }
        if(i % 2 == 0){
            temp = l;
            l = l->next;
            temp->next = cur->next;
            cur->next = temp;
        }
        cur = cur->next;
        i++;
    }
    if(l != NULL){
        cur->next = l;
    }
    return new_head->next;
}

import java.util.Scanner;
public class Main{
    static class ListNode{
        int data;
        ListNode next;
        public ListNode(int data){
            this.data = data;
            this.next = null;
        }
    }
    public static void printList(ListNode list){
        ListNode ref = list;
        if(ref == null){
            System.out.println();
            return;
        }
        StringBuilder result = new StringBuilder("");
        while(ref != null){//优化printList之后，测试用例直接从75% ->100%成功跑过所有测试用例
            result.append(ref.data).append(" ");
            //System.out.print( ref.data + " ");
            ref = ref.next;
        }
        System.out.println(result.toString());
    }
    public static ListNode refactorLinkedList(ListNode list){
        if(list == null || list.next == null || list.next.next == null){
            return list;
        }
        ListNode leftSection = list;
        ListNode rightSection = list;
        ListNode slow = list;
        ListNode fast = list;
        ListNode rear = null;
        while(fast != null && fast.next != null){
            rear = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        rear.next = null;
        rightSection = slow;
        ListNode temp;
        while(leftSection.next != null){
            temp = leftSection.next;
            leftSection.next = rightSection;
            rightSection = rightSection.next;//
            leftSection.next.next = temp;
            leftSection = temp;
        }
        leftSection.next = rightSection;
        return list;
    }
    public static void main(String[] args){
        ListNode list = null;
        ListNode tail = null;
        Scanner scanner = new Scanner(System.in);
        int num = Integer.parseInt(scanner.nextLine());
        String input = scanner.nextLine();
        String[] para = input.split("\\p{javaWhitespace}+");
        ListNode node = new ListNode(Integer.parseInt(para[0]));
        list = node;
        tail = node;
        for(int i = 1; i < num; i++){//优化初始化单链表的代码之后，测试用例从25 pecrcent -> 75 percent.
            node = new ListNode(Integer.parseInt(para[i]));
            tail.next = node;
            tail = node;
        }
        list =refactorLinkedList(list);
        printList(list);
        scanner.close();
    }
}

# include <bits/stdc++.h>
using namespace std;

struct list_node{
    int val;
    struct list_node * next;
};


list_node * input_list(void)
{
    int n, val;
    list_node * phead = new list_node();
    list_node * cur_pnode = phead;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &val);
        if (i == 1) {
            cur_pnode->val = val;
            cur_pnode->next = NULL;
        }
        else {
            list_node * new_pnode = new list_node();
            new_pnode->val = val;
            new_pnode->next = NULL;
            cur_pnode->next = new_pnode;
            cur_pnode = new_pnode;
        }
    }
    return phead;
}


list_node * relocate(list_node * head)                   //占用内存70M.......
{
    //////在下面完成代码
    int i=0,flag=0;
    list_node *new_head,*head1,*head2,*head3,*first;
    new_head=new list_node();
    head1=new list_node();
    head2=new list_node();
    head3=new list_node();
    first=new list_node();
    new_head=head;
    while(head!=NULL)
    {
        flag++;
        head=head->next;
    }
    head=new_head;
    head3->val=0;
    head3->next=NULL;
    first=head3;
    if(flag%2==0)
    {
        for(i=0;i<flag/2;i++)
        {
            head=head->next;
        }
        head2=head;
        head1=new_head;
        head=new_head;
        for(i=0;i<flag/2;i++)
        {
            list_node *temp1=new list_node();
            temp1->val=head1->val;
            temp1->next=NULL;
            head3->next=temp1;
            head3=head3->next;
            list_node * temp2=new list_node();
            temp2->val=head2->val;
            temp2->next=NULL;
            head3->next=temp2;
            head3=head3->next;
            head1=head1->next;
            head2=head2->next;
        }
    }
    else if(flag%2!=0)
    {
        for(i=0;i<flag/2;i++)
        {
            head=head->next;
        }
        head2=head;
        head1=new_head;
        head=new_head;
        for(i=0;i<flag/2;i++)
        {
            list_node *temp1=new list_node();
            temp1->val=head1->val;
            temp1->next=NULL;
            head3->next=temp1;
            head3=head3->next;
            list_node *temp2=new list_node();
            temp2->val=head2->val;
            temp2->next=NULL;
            head3->next=temp2;
            head3=head3->next;
            head1=head1->next;
            head2=head2->next;
        }
        head3->next=head2;
    }
    first=first->next;
    return first;
}


void print_list(list_node * head)
{
    while (head != NULL) {
        printf("%d ", head->val);
        head = head->next;
    }
    puts("");
}


int main ()
{
    list_node * head = input_list();
    list_node * new_head = relocate(head);
    print_list(new_head);
    return 0;
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static class Node {

        public int value;
        public Node next;

        public Node(int value) {
            this.value = value;
        }
    }
    
    public static Node listGenerator(int length, String[] numbers) {
        Node head = new Node(Integer.parseInt(numbers[0]));
        Node cur = head;
        for (int i = 1; i < length; i++) {
            cur.next = new Node(Integer.parseInt(numbers[i]));
            cur = cur.next;
        }
        cur.next = null;
        return head;
    }
    
    public static void printList(Node head) {
        while (head != null) {
            System.out.print(head.value +" ");
            head = head.next;
        }
        System.out.println();
    }
    
    public static void relocate(Node head) {
        if (head == null || head.next == null) {
            return;
        }
        Node fast = head.next;
        Node slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        fast = slow.next;
        slow.next = null;
        mergeLR(head, fast);
    }

    private static void mergeLR(Node left, Node right) {
        Node next;
        while (left.next != null) {
            next = left.next;
            left.next = right;
            right = right.next;
            left.next.next = next;
            left = next;
        }
        left.next = right;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bufferedReader.readLine());
        String[] numbers = bufferedReader.readLine().split(" ");
        Node head = listGenerator(n, numbers);
        relocate(head);
        printList(head);
    }
}