补上昨天的题 力扣143：链表重排 给定一个单链表 L：L0→L1→…→Ln-1→Ln ， 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→… 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。 方法一：使用链表的基本操作
解题思路： 1、使用快慢指针，得到两个链表 2、将后半部分的链表反转 3、将反转后的链表插入前半部分的链表缝隙java代码：`
class Solution { public void reorderList(ListNode head) { if(head == null || head.next == null) return ; ListNode slow= head,fast = head; while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; } ListNode lastNode = slow.next; slow.next = null; lastNode = Reverse(lastNode); ListNode firstNode = head; while(firstNode!=null && lastNode!=null){ ListNode front = firstNode.next; ListNode later = lastNode.next; firstNode.next = lastNode; firstNode = front; lastNode.next = firstNode; lastNode = later; } } public ListNode Reverse(ListNode head){ if(head == null || head.next == null) return head; ListNode newhead = Reverse(head.next); head.next.next = head; head.next = null; return newhead; } }后来看了一下官方题解，使用多个方法比较清晰一点，下附代码
class Solution { public void reorderList(ListNode head) { if (head == null) { return; } ListNode mid = middleNode(head); ListNode l1 = head; ListNode l2 = mid.next; mid.next = null; l2 = reverseList(l2); mergeList(l1, l2); } public ListNode middleNode(ListNode head) { ListNode slow = head; ListNode fast = head; while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; } return slow; } public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode curr = head; while (curr != null) { ListNode nextTemp = curr.next; curr.next = prev; prev = curr; curr = nextTemp; } return prev; } public void mergeList(ListNode l1, ListNode l2) { ListNode l1_tmp; ListNode l2_tmp; while (l1 != null && l2 != null) { l1_tmp = l1.next; l2_tmp = l2.next; l1.next = l2; l1 = l1_tmp; l2.next = l1; l2 = l2_tmp; } } }