#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需要指向nullnode.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. 反转链表的方法
  等