题解 | #重排链表#

/**

Definition for singly-linked list.
class ListNode {
```
int val;
```
```
ListNode next;
```
```
ListNode(int x) {
```
```
    val = x;
```
```
    next = null;
```
```
}
```

} */ public class Solution { public void reorderList(ListNode head) { int count = 0;//计数器，统计链表节点的数量 ListNode head0 = head;//创建一个临时头节点，head永远指向头节点，返回值始终都是head while(head0 != null){ count++;//计数器加1 head0 = head0.next;//链表后移 } head0 = head;//重置链表头节点 //特殊值处理，当链表为空，或者链表的数量小于等于2时，返回自身链表。 if(head == null || count<=2){ while(head0 != null){ head0 = head0.next; } return; }

 //链表数量的一半值，再减一，用于对半截取链表，且指针指向第一个链表的最后一个节点
 int len = (count+1)/2 - 1;
 int count0 = 0;
 while(count0 < len){
     head0 = head0.next;
     count0++;
 }
 ListNode tail2 = head0.next;//tail2此时指向第2个链表的头节点
 ListNode tail1 = head0;//tail1此时指向第1个链表的尾节点
 head0.next = null;//将链表从中间断开，第1个链表为[head,tail1],第1个链表为[tail2,开始时的链表的最后一个节点]
 ListNode head1 = head;//head1此时指向第1个链表的头节点
 //反转链表2
 ListNode head2 = tail2;//head2此时指向第2个链表的头节点
 ListNode prev2 = null;
 ListNode next2 = null;
 while(head2 != null){
     next2 = head2.next;
     head2.next = prev2;
     prev2 = head2;
     head2 = next2;
 }
 //循环结束后，prev2此时指向第2个链表的头节点，tail2此时指向第2个链表的尾节点
 head2 = prev2;
 count0 = 0;
 ListNode next1 = null;
 if(count%2 == 0){
     len++;
 }
 //两个链表相连
 while(count0 < len){
     next1 = head1.next;
     head1.next = head2;
     head1 = next1;
     next2 = head2.next;
     head2.next = head1;
     head2 = next2;
     count0++;
 }

} }