Offer26：重排链表

Offer26：重排链表

---

1. 题目描述

• 给定一个单链表 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. 解答分析

• 分析： 这题不难发现，最后需要输出的链表其实是前半部分和后半部分的翻转,接着再头连着头，依次进行排序输出。

  • 所以最原始的方法是需要3个不同的函数功能。
    1. reorderList()函数：主函数，用于均分两半链表，并将它们进行操作。
    2. ``reverse()`函数：翻转后半部分的链表。
    3. link()函数：用于连接前半部分链表、后半部分链表。

  ---

• 代码：

  class Solution{
      public void recorderList(ListNode head){
          ListNode dummy=new ListNode(0);
          dummy.next=head;//哨兵
          ListNode fast=dummy;//快指针
          ListNode slow=dummy;//慢指针
         while(fast!=null && fast.next!=null){
             slow=slow.next;
             fast=fast.next.next;
         }
          
          ListNode temp=slow.next;//中间节点的指针暂定为temp
          slow.next=null;//准备连接，slow.next为空了
          link(head,reverse(temp),dummy);//开始连接
      }
      private ListNode reverse(ListNode head){//反转链表，注意指针的指向位置
          ListNode prev=null;
          ListNode cur=head;
          while(cur!=null){
              ListNode next=cur.next;
              cur.next=prev;
              prev=cur;
              cur=next;
          }
          return prev;
      }
      private void link(ListNode node1,ListNode node2,ListNode head){//借助原链表的头结点head（在本题函数中指的是哨兵节点dummy）,按照题目要求连接前后两部分，新链表的头节点为prev
          ListNode prev=head;
          while(node1!=null && node2!=null){
              ListNode temp=node1.next;//当前node1节点的下一个位置为temp
              
             	prev.next=node1;//prev指针指向node1部分第一个节点
              node1.next=node2;//node1后面连的是反转后node2的第一个
              prev=node2;//prev开始下一次连接
              
              node1=temp;//node1后移
              node2=node2.next;//node2后移
          }
          if(node1!=null){
              prev.next=node1;//这一个if是用来判断前半部分链表必须比后半部分多，当node1无法匹配连接node2时，直接连接返回node1的节点值。
          }
      }
  }

  ---

3. 思考总结

• 思考： 其实代码不用写三个函数，用在一个函数内部即可，不需要来回调用，实现折半翻转再重连即可。代码如下：

  class Solution {
      public void reorderList(ListNode head) {
          ListNode f = head, s = head;
          while (f.next != null && f.next.next != null) {
              s = s.next;//慢指针找到中间的节点
              f = f.next.next;//快指针直接到末尾节点
          }
  
          ListNode t = s.next;//暂存的t节点是慢指针的下一位
          f=null;//快指针此时位于最后一个节点，赋值为空
          while (t != null) {//翻转
              t = s.next;
              s.next = f;
              f = s;
              s = t;
          }
          s = head;//这里是将后半部分翻转。此时快指针指向原链表的最后一位元素
  
          while (s != null) {//再重新进行连接
              t = s.next;//保留当前位置的下一位
              s.next = f;//后半部分的最后一位
              s = f;
              f = t;
          }
      }
  }

  ---

  END