【CodeTop 02】2024-07-30 - 143.重排链表

[larscheng]

143. 重排链表

[larscheng]

思路

• 快慢指针找到中间节点，然后将中间节点及其后节点放入栈

• 将栈中节点依次取出，插入到原链表对应每个节点之后

  代码

  
  class Solution {
  /**
   * 1，2，3，4，5
   * 1，5，2，4，3
   *
   * 快慢指针找到中间节点，然后将中间节点及其后节点放入栈
   * 将栈中节点依次取出，插入到原链表对应每个节点之后
   */
  public void reorderList(ListNode head) {
      ListNode slow = head;
      ListNode fast = head;
      //循环结束，slow为中间节点
      while (fast!=null&&fast.next!=null) {
          slow=slow.next;
          fast=fast.next.next;
      }
  
      Stack<ListNode> stack = new Stack<>();
      while (slow!=null) {
          stack.push(slow);
          slow = slow.next;
      }
  
      //ListNode dummy = new ListNode(0,head);
      //ListNode point = dummy.next;
      swap(stack, head);
  
  }
  
  private void swap(Stack<ListNode> stack, ListNode point) {
      ListNode popNode;
      while (!stack.isEmpty()) {
          popNode = stack.pop();
          //point等于popNode:已经到最后一个节点（奇数个）
          //point.next等于popNode:左侧最后一个节点（偶数个）
          if (point == popNode || point.next == popNode) {
              popNode.next=null;
              break;
          }
  
          popNode.next = point.next;
          point.next = popNode;
  
          point = point.next.next;
      }
  }
  }

### 复杂度
- 时间复杂度：O(n)
- 空间复杂度：O(n)