翻转链表

import java.io.*;
import java.util.Scanner;

// 链表中点 + 后半链表反转 + 建链表 【锻炼 链表操作】

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] sp = br.readLine().split(",");
        int[] a = new int[sp.length];
        for (int i = 0; i < sp.length; i++) a[i] = Integer.parseInt(sp[i]);

        //1、获取链表
        ListNode head = new ListNode(-1), slow = head, fast = head;
        head.next = getList(a);
        //2、找到链表中点
        while (fast != null) {
            fast = fast.next;
            slow = slow.next; // slow即中点（奇&nbs***bsp;偶 [左边那个] ）
            if (fast != null) fast = fast.next;
        }
        //3、反转后半链表
        ListNode pre = null, cur = slow.next, next = null; // 前、当前、后
        slow.next = null; // 🍓 中点结扎
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur; // pre即链表尾节点
            cur = next;
        }
        //4、交替插入链表
        ListNode p = head.next, q = pre; // p头 q尾, 逼近
        while (q != null) {
            ListNode pnext = p.next, qnext = q.next;
            p.next = q;
            q.next = pnext;
            p = pnext;
            q = qnext;
        }
        //5、遍历链表得结果
        StringBuilder res = new StringBuilder();
        p = head.next;
        while (p != null) {
            res.append(p.val);
            p = p.next;
            if (p != null) res.append(",");
        }
        System.out.print(res.toString());
    }

    /** 建链表 */
    private static ListNode getList(int[] a) {
        ListNode head = new ListNode(-1), tail = head;
        for (int val : a) {
            ListNode p = new ListNode(val);
            tail.next = p;
            tail = p;
        }
        return head.next;
    }
}

/** 链表节点 */
class ListNode {
    int val;
    ListNode next;
    public ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

练习链表输入输出

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;
        }

    }

}