题目

类型：Stack

难度：中等

重排链表 - 图1

解题思路

目标链表即为将原链表的左半端和反转后的右半端合并后的结果。

即可划分为三步：

1、找到原链表的中点

我们可以使用快慢指针来找到链表的中间节点

2、将原链表的右半端反转

我们可以使用迭代法实现链表的反转。

3、将原链表的两端合并。

因为两链表长度相差不超过 11，因此直接合并即可。

代码

  1. class Solution {
  2.     public void reorderList(ListNode head) {
  3.         if (head == null) {
  4.             return;
  5.         }
  6.         ListNode mid = middleNode(head);
  7.         ListNode l1 = head;
  8.         ListNode l2 = mid.next;
  9.         mid.next = null;
  10.         l2 = reverseList(l2);
  11.         mergeList(l1, l2);
  12.     }
  14.     public ListNode middleNode(ListNode head) {
  15.         ListNode slow = head;
  16.         ListNode fast = head;
  17.         while (fast.next != null && fast.next.next != null) {
  18.             slow = slow.next;
  19.             fast = fast.next.next;
  20.         }
  21.         return slow;
  22.     }
  24.     public ListNode reverseList(ListNode head) {
  25.         ListNode prev = null;
  26.         ListNode curr = head;
  27.         while (curr != null) {
  28.             ListNode nextTemp = curr.next;
  29.             curr.next = prev;
  30.             prev = curr;
  31.             curr = nextTemp;
  32.         }
  33.         return prev;
  34.     }
  36.     public void mergeList(ListNode l1, ListNode l2) {
  37.         ListNode l1_tmp;
  38.         ListNode l2_tmp;
  39.         while (l1 != null && l2 != null) {
  40.             l1_tmp = l1.next;
  41.             l2_tmp = l2.next;
  43.             l1.next = l2;
  44.             l1 = l1_tmp;
  46.             l2.next = l1;
  47.             l2 = l2_tmp;
  48.         }
  49.     }
  50. }