程式員代碼面試指南刷題--第二章.按照左右半區的方式重新組合單連結清單

題目描述

給定一個單連結清單的頭部節點 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

解法一：我的

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

public class Main{
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static ListNode change(ListNode head){
        if(head==null||head.next==null) return head;
        ListNode tmp = head;
        int count = 0;
        while(tmp!=null){
            count++;
            tmp = tmp.next;
        }
        count = count/2;
        tmp = head;
        for(int i=0;i<count;i++){
            tmp = tmp.next;
        }
        ListNode newlist = new ListNode(0);
        ListNode r = newlist; 
        for(int i=0;i<count;i++){
            r.next = head;
            ListNode node = head.next;
            head.next = tmp;
            head = node;
            r = tmp;
            tmp = tmp.next;
        }
        return newlist.next;
    }
    public static ListNode creat() throws IOException{
        int size = Integer.parseInt(br.readLine());
        String[] ss = br.readLine().trim().split(" ");
        ListNode head = new ListNode(0);
        ListNode r = head;
        for(int i=0;i<size;i++){
            ListNode node = new ListNode(Integer.parseInt(ss[i]));
            r.next = node;
            r = node;
        }
        return head.next;
    }
    public static void main(String[] args) throws IOException{
        ListNode head = creat();
        head = change(head);
        while(head!=null){
            System.out.print(head.val+" ");
            head=head.next;
        }
    }        
}
class ListNode{
    int val;
    ListNode next;
    public ListNode(int val){
        this.val = val;
        this.next = null;
    }
}
           

解法二：優化一下找中間節點的代碼

思路： 當隻有兩個節點mid是第一個節點，當連結清單長度大于二時，每增加兩個節點mid向後推一個。

Node mid = head;
Node right = head.next;
while(right.next!=null&&right.next.next!=null){
	mid = mid.next;
	right = right.next.next;
}
right = mid.next;  //可求
           

具體：

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int len = Integer.parseInt(br.readLine());
        String[] arr = br.readLine().trim().split(" ");
        ListNode root = new ListNode(-1);
        for(int i=len-1;i>=0;i--){
            ListNode node = new ListNode(Integer.parseInt(arr[i]));
            node.next = root.next;
            root.next = node;
        }
        root = change(root.next);
        StringBuilder sb = new StringBuilder();
        while(root!=null){
            sb.append(root.val+" ");
            root = root.next;
        }
        System.out.println(sb.toString().trim());
    }
    public static ListNode change(ListNode root){
        if(root==null||root.next==null||root.next.next==null) return root;
        ListNode pre = root;
        ListNode last = root;
        //找一半
        while(last.next!=null&&last.next.next!=null){
            pre = pre.next;
            last = last.next.next;
        }
        if(last.next!=null) pre = pre.next;
        ListNode flag = pre;
        ListNode r = root;
        while(r.next!=flag){
            last = pre.next;
            pre.next = r.next;
            r.next = pre;
            r = pre.next;
            pre = last;
        }
        r.next = pre;
        return root;
    }
}
class ListNode{
    int val;
    ListNode next;
    public ListNode(int val){
        this.val = val;
    }
}