#LeetCode每日一题【链表专题】

• 重排链表
  https://leetcode-cn.com/problems/reorder-list/

• 分析
  需要将一个链表按照（i，n-i）的顺序重新排列
  1->n-1->2->n-2->3->n-3…

• 实现一
  难点在于找到i位置对应的n-i位置的节点，首先容易想到的是利用辅助空间栈或者列表，按顺序储存各节点，再一个个拿出来与原链表组合、调整位置

  public void reorderList(ListNode head) {
         if (head == null || head.next == null) {
             return;
         }
         // 第一篇遍历、将链表节点依次入栈，同时记录链表的长度
         int length = 0;
         Stack<ListNode> stack = new Stack<>();
         ListNode temp = head;
         while (temp != null) {
             stack.push(temp);
             temp = temp.next;
             length++;
         }
         // 第二次只需要遍历length/2 且同时逐个出栈，再调整位置
         ListNode node = head, next;
         length = length / 2;
         while (length > 0) {
             next = node.next;
             ListNode pop = stack.pop();
             node.next = pop;
             pop.next = next;
             node = next;
             length--;
         }
         // 最后一个节点的next需要指向null
         node.next = null;
     }
  

  LeetCode耗时：3ms
  

• 实现二
  不使用辅助空间：
  双指针找到链表的中点
  根据中点将链表分成两部分，并且将第二部分进行反转
  遍历两个链表+调整位置

  public void reorderList02(ListNode head) {
      if (head == null || head.next == null) {
          return;
      }
      // 快指针两倍于慢指针向前，到最后慢指针位置即为链表中点
      ListNode slow = head, fast = head;
      while (fast != null && fast.next != null) {
          slow = slow.next;
          fast = fast.next.next;
      }
      // 分成两个链表以及反转后半段链表
      fast = slow.next;
      slow.next = null;
  
      ListNode prev = null, next;
      while (fast != null) {
          next = fast.next;
          fast.next = prev;
          prev = fast;
          fast = next;
      }
  
      // 重新调整位置
      ListNode next2, node = head;
      while (prev != null) {
          next = node.next;
          next2 = prev.next;
          node.next = prev;
          prev.next = next;
          node = next;
          prev = next2;
      }
      System.out.println(head);
  }
  

  LeetCode耗时：1ms
  

• 小结
  正常思路下：关于链表的很多题目都可以使用辅助空间解决
  但是有时双指针等一些其他技巧可以代替辅助空间的使用；
  
  
  其次在第二种方式中，综合运用了很多关于链表的操作技巧：
  a. 双指针寻找链表的链表中点（寻找链表到处第n个节点）
  b. 反转链表的方法
  等