题目描述

给定一个单链表 L 的头节点 head ,单链表 L 表示为:

L0 → L1 → … → Ln-1 → Ln
请将其重新排列后变为:

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

示例

image-20211007213445816

输入: head = [1,2,3,4,5]
输出: [1,5,2,4,3]

数据范围

  • 链表的长度范围为 [1, 5 * 104]
  • 1 <= node.val <= 1000

题解

  1. 找到链表中点
    1. 通过快慢指针,快指针每次走两步,慢指针每次走一步
    2. 当快指针为空或快指针下一个节点为空时,慢节点所在位置即为链表中点
    3. 当链表为偶数时,慢指针所在位置为中点靠后的位置
  2. 将链表按中点分为两部分,记为A,B
  3. 对后半部分进行反转
  4. 对两块链表做归并操作
    1. 分别记录两链表next指针位置,A_next = A.next,B_next = B.next
    2. A.next = B,A = A_next
    3. B.next = A,B = B_next

Code

/**
* 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;
}
//找到链表中点
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}
//将中间节点右侧节点反转
ListNode tem = slow.next;
slow.next = null;
ListNode newHead = reverse(tem);
//元素交换
ListNode cur = head;
while(cur != null && newHead != null){
ListNode l1_next = cur.next;
ListNode l2_next = newHead.next;

cur.next = newHead;
cur = l1_next;
newHead.next = cur;
newHead = l2_next;
}
}
public ListNode reverse(ListNode head){
if(head == null || head.next == null){
return head;
}
ListNode last = reverse(head.next);
head.next.next = head;
head.next = null;
return last;
}
}