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

本文主要是介绍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;}
}