翻转链表

练习链表输入输出

import java.util.*;
import java.io.*;
public class Main{

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

    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        String[] s = str.split(",");
        ListNode head = new ListNode(0);
        ListNode tail = head;
        for(String _s : s){
            ListNode newNode = new ListNode(Integer.parseInt(_s));
            tail.next = newNode;
            tail = newNode;
        }
        reorderList(head.next);
        head = head.next;

        while(head != null){
            if(head.next == null) System.out.print(head.val);
            else System.out.print(head.val + ",");
            head = head.next;
        }

    }
    //找到链表中点，反转链表，合并两个链表
    public static void reorderList(ListNode head){
        if(head == null || head.next == null) return;
        ListNode mid = getMid(head);
        ListNode l2 = mid.next;
        l2 = reverseList(l2);
        mid.next = null;
        merge(head, l2);
    }

    //找到链表中点
    public static ListNode getMid(ListNode node){
        ListNode s = node, f = node;
        while(f != null && f.next != null){
            s = s.next;
            f = f.next.next;
        }
        return s;
    }

    //反转链表
    public static ListNode reverseList(ListNode node){
        ListNode pre = null;
        ListNode cur = node;
        while(cur != null){
            ListNode ne = cur.next;
            cur.next = pre;
            pre = cur;
            cur = ne;
        }
        return pre;
    }

    //合并连个链表
    public static void merge(ListNode l1, ListNode l2){
        ListNode p1 = l1, p2 = l2;
        while(l1 != null && l2 != null){
            p1 = l1.next; p2 = l2.next;
            l1.next = l2; l1 = p1;
            l2.next = l1; l2 = p2;
        }
    }
}

import java.util.Scanner;

/*
题目描述：对于一个链表 L: L0→L1→…→Ln-1→Ln,将其翻转成 L0→Ln→L1→Ln-1→L2→Ln-2→…
输入1,2,3,4,5     输出1,5,2,4,3
备注：数组长度不超过100000
 */
public class Main {
    //定义Node节点
    static class ListNode {
        int val;
        ListNode next = null;

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

    public static void main(String[] args) {
        //1.获取控制台输入的信息
        Scanner scanner = new Scanner(System.in);
        String string = scanner.nextLine();
        String[] strings = string.split(",");
        //2.将输入的字符串构成带头节点的2个链表
        ListNode head = creatList(strings);
        reorderList(head.next);
        head = head.next;
        //3.输出
        while(head!=null){
            if(head.next==null){
                System.out.print(head.val);
            }else{
                 System.out.print(head.val+",");
            }
            head=head.next;
        }

    }



    /*
     * 将str创建带头结点的单链表
     */
    public static ListNode creatList(String[] strings) {
        ListNode head = new ListNode(0);
        ListNode tail = head;
        for (String str : strings) {
            ListNode newNode = new ListNode(Integer.valueOf(str));
            tail.next = newNode;
            tail = newNode;
        }
        return head;
    }


    /*
     * 思路：链表平均拆分，后半部分链表反转，在将两个链表合并
     */
    public static void reorderList(ListNode head) {
        if (head == null || head.next == null) return;

        ListNode p1 = head;
        ListNode p2 = head;

        // 找到链表的一半
        while (p2.next != null && p2.next.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
        }

        // 将链表分为两段
        p2 = p1.next;
        p1.next = null;
        p1 = head;

        // 将后半段进行链表的翻转
        ListNode head2 = p2;
        ListNode next2;
        while (p2.next != null) {
            next2 = p2.next;
            p2.next = next2.next;
            next2.next = head2;
            head2 = next2;
        }
        p2 = head2;

        // 两条链表进行合并
        ListNode next1;
        while (p2 != null) {
            next1 = p1.next;
            next2 = p2.next;

            p1.next = p2;
            p2.next = next1;

            p1 = next1;
            p2 = next2;
        }

    }

}