Leetcode-高频面试题-143.重排链表

 解法都在代码里，不懂就留言或者私信

/**  * Definition for singly-linked list.  * public class ListNode {  *     int val;  *     ListNode next;  *     ListNode() {}  *     ListNode(int val) { this.val = val; }  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }  * }  */ class Solution {     /**本题基本思路：先把链表分为前半部分和后半部分，如果不是偶数就前半部分多一个     然后把后半部分逆序，然后前后一个一个的交替连接*/     public void reorderList(ListNode head) {         if(head == null || head.next == null) {             return;         }         /**先过一下链表统计一下节点数 */         int count = 0;         ListNode cur = head;         while(cur != null) {             count ++;             cur = cur.next;         }         /**把cur恢复成指向head*/         cur = head;         /**count变成（count-1）/2 */         count = (count - 1)/2;         while(count > 0) {             cur = cur.next;             count --;         }         /**出while循环的时候cur指向的是左边部分的终点，现在开始分离链表的工作 */         ListNode rightHead = cur.next;         cur.next = null;         /**再次把cur恢复成head */         cur = head;         rightHead = reverse(rightHead);         /**head肯定是要作为头的，我们现在要用一个left指针指向head的下个节点（左边部分的下一个节点） */         ListNode left = head.next;         ListNode right = rightHead;         /**当前已经串起来的最后一个节点 */         ListNode curNode = head;         while(left != null) {             /**每次循环我们只处理两个数，先连右边部分下一个，然后右边部分下一个指向左边下一个             这个过程就造成了右边部分下一个指针发生变化，需要提前存一下，左边部分是我们串的最后一个节点             它的next不变，不用执行这个操作 */             ListNode rightNext = right.next;             /**之前最后一个节点(来自左边)连接右边下一个节点 */             curNode.next = right;             /**右边下一个的next指向左边下一个 */             right.next = left;             /**本次循环的最后一个节点作为curNode（最后一个被串起来的节点） */             curNode = left;             /**左右都跳下一个 */             right = rightNext;             left = left.next;             }         /**如果没有用完，只能是右边没有用完 */         if(right != null) {             curNode.next = right;             right.next = null;         }     }     /**经典面试题-反转链表 */     public ListNode reverse(ListNode head) {         ListNode cur = head;         ListNode pre = null;         ListNode next = null;         while(cur != null) {             next = cur.next;             cur.next = pre;             pre = cur;             cur = next;         }         return pre;     } }