Article From:https://www.cnblogs.com/goPanama/p/9496090.html
 1 class Solution {
 2    public void reorderList(ListNode head) {
 3        if(head == null) return;
 4        if(head.next == null) return;
 5        if(head.next.next == null) return;
 6        ListNode node1 = head;
 7        ListNode node2 = head;
 8       while(node2.next != null && node2.next.next != null) {
 9           node2 = node2.next.next;
10           node1 = node1.next;
11       }
12       ListNode head2 = node1.next;
13       node1.next = null;   //The end of the first half should be divided into two separate LinkedList.14       //Reverse head2 list
15       ListNode p1 = head2;
16       ListNode p2 = head2;
17       ListNode p3 = head2;
18       while(p2 != null) {
19           p3 = p3.next;
20           if(head2 == p2) {
21               p2.next = null;
22               p2 = p3;
23           }else {
24               p2.next = p1;
25               p1 = p2;
26               p2 = p3;  
27           }
28           
29       }
30       head2 = p1;
31       
32       ListNode tmp1 = head, head1 = head;
33       ListNode tmp2 = head2;
34       while(tmp2 != null && tmp1 != null) {
35           tmp1 = tmp1.next;
36           tmp2 = tmp2.next;
37           head1.next = head2;
38           head2.next = tmp1;
39           head1 = tmp1;
40           head2 = tmp2;
41           
42       }
43      return;  
44        
45    }
46 }

 

Similar Posts:

Link of this Article: 143. Reorder List (LL)

Leave a Reply

Your email address will not be published. Required fields are marked *