Question

剑指 Offer II 026. 重排链表

题目描述

给定一个单链表 L_ _的头节点 head ，单链表 L 表示为：

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

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

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

 

示例 1:

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

示例 2:

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

 

提示：

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

 

注意：本题与主站 143 题相同：https://leetcode.cn/problems/reorder-list/ 

解法

方法一

# Definition for singly-linked list.
# class ListNode:
#   def __init__(self, val=0, next=None):
#     self.val = val
#     self.next = next
class Solution:
  def reorderList(self, head: ListNode) -> None:
    mid = self.middleNode(head)
    tmp = mid.next
    mid.next = None
    tmp = self.reverseList(tmp)
    head = self.mergeTwoLists(head, tmp)

  def middleNode(self, head: ListNode) -> ListNode:
    slow, fast = head, head
    while fast and fast.next:
      slow = slow.next
      fast = fast.next.next
    return slow

  def reverseList(self, head: ListNode) -> ListNode:
    pre, cur = None, head
    while cur:
      tmp = cur.next
      cur.next = pre
      pre = cur
      cur = tmp
    return pre

  def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
    dummy = ListNode()
    cur = dummy
    while l1 and l2:
      cur.next = l1
      l1 = l1.next
      cur = cur.next
      cur.next = l2
      l2 = l2.next
      cur = cur.next
    cur.next = l1 or l2
    return dummy.next

/**
 * 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) {
    ListNode mid = middleNode(head);
    ListNode tmp = mid.next;
    mid.next = null;
    tmp = reverseList(tmp);
    head = mergeTwoLists(head, tmp);
  }

  private ListNode middleNode(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
      slow = slow.next;
      fast = fast.next.next;
    }
    return slow;
  }

  private ListNode reverseList(ListNode head) {
    ListNode pre = null, cur = head;
    while (cur != null) {
      ListNode tmp = cur.next;
      cur.next = pre;
      pre = cur;
      cur = tmp;
    }
    return pre;
  }

  private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode();
    ListNode cur = dummy;
    while (l1 != null && l2 != null) {
      cur.next = l1;
      l1 = l1.next;
      cur = cur.next;
      cur.next = l2;
      l2 = l2.next;
      cur = cur.next;
    }
    cur.next = l1 != null ? l1 : l2;
    return dummy.next;
  }
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *   int val;
 *   ListNode *next;
 *   ListNode() : val(0), next(nullptr) {}
 *   ListNode(int x) : val(x), next(nullptr) {}
 *   ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
  void reorderList(ListNode* head) {
    ListNode* mid = middleNode(head);
    ListNode* tmp = mid->next;
    mid->next = nullptr;
    tmp = reverseList(tmp);
    head = mergeTwoLists(head, tmp);
  }

  ListNode* middleNode(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next) {
      slow = slow->next;
      fast = fast->next->next;
    }
    return slow;
  }

  ListNode* reverseList(ListNode* head) {
    ListNode* pre = nullptr;
    ListNode* cur = head;
    while (cur) {
      ListNode* tmp = cur->next;
      cur->next = pre;
      pre = cur;
      cur = tmp;
    }
    return pre;
  }

  ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode* dummy = new ListNode();
    ListNode* cur = dummy;
    while (l1 && l2) {
      cur->next = l1;
      l1 = l1->next;
      cur = cur->next;
      cur->next = l2;
      l2 = l2->next;
      cur = cur->next;
    }
    cur->next = l1 ? l1 : l2;
    return dummy->next;
  }
};

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *   Val int
 *   Next *ListNode
 * }
 */
func reorderList(head *ListNode) {
  mid := middleNode(head)
  tmp := mid.Next
  mid.Next = nil
  tmp = reverseList(tmp)
  head = mergeTwoLists(head, tmp)
}

func middleNode(head *ListNode) *ListNode {
  slow, fast := head, head
  for fast != nil && fast.Next != nil {
    slow = slow.Next
    fast = fast.Next.Next
  }
  return slow
}

func reverseList(head *ListNode) *ListNode {
  var pre *ListNode
  cur := head
  for cur != nil {
    tmp := cur.Next
    cur.Next = pre
    pre = cur
    cur = tmp
  }
  return pre
}

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
  dummy := new(ListNode)
  cur := dummy
  for l1 != nil && l2 != nil {
    cur.Next = l1
    l1 = l1.Next
    cur = cur.Next
    cur.Next = l2
    l2 = l2.Next
    cur = cur.Next
  }
  if l1 != nil {
    cur.Next = l1
  }
  if l2 != nil {
    cur.Next = l2
  }
  return dummy.Next
}