Solution 1: Use the pointer properties of arrays to recreate the desired listCopy the code

Solution 1: brute force cracking

/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ import java.util.*; public class Solution { public void reorderList(ListNode head) { if(head == null) return; LinkedList<ListNode> list = new LinkedList<>(); ListNode temp = head; while(temp! =null){ list.add(head); temp=temp.next; } int i=0,j=list.size()-1; while(i<j){ list.get(i).next=list.get(j); i++; if(i==j){ break; } list.get(j). Next =list.get(I);} list.get(j). j--; } list.get(i).next=null; // The next node to the last node is null}}Copy the code
Solution 2 Split the linked list into two lists, flip the second half, and join the two listsCopy the code

Solution 2: Split the linked list

/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ import java.util.*; public class Solution { public void reorderList(ListNode head) { if(head == null||head.next==null||head.next.next==null)  return; ListNode slow=head; ListNode slow=head; ListNode fast=head.next; while(fast ! =null && fast.next! =null){ slow=slow.next; fast=fast.next.next; } ListNode mid = slow.next; slow.next=null; ListNode newHead= reverse(mid); while(newHead! =null){ ListNode temp =newHead.next; newHead.next=head.next; head.next=newHead; head=newHead.next; newHead=temp; } } public ListNode reverse(ListNode head){ if(head == null) return head; ListNode pre=null; ListNode temp=null; while(head! =null){ temp=head.next; head.next=pre; pre=head; head=temp; } return pre; }}Copy the code