大厂面试-美团高频考察算法之重排链表

本文学习目标或巩固的知识点

• 学习如何处理链表重排类题目
  • 巩固反转链表
  • 巩固快慢指针
  • 巩固合并链表

    ---

    提前说明：算法题目来自力扣、牛客等等途径

    🟢表示简单

    🟡表示中等

    🔴表示困难

    🤮表示恶心

    博主真实经历，该题在美团到店，美团地图部门一面均有考察！！！！！！一般大厂面试的做题时间也就10-30分钟左右，如果不经常练习或者没掌握技巧很容易栽倒到一些容易的题上面，等回头看只有空悲切！！！！掌握技巧和算法敏感度很重要！！！！！

    LCR 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]
      

      通过题目可知

      1. 链表合并后链表的头节点不变，不用考虑链表头结点问题
      2. 链表重排后规律是第一个结点跟倒数第一个结点、第二个结点跟倒数第二个结点，依次
         1. 可分成两个链表然后合并，然后考虑如何合并？考察基础：合并两个链表
         2. 第二个链表怎么分出来？快慢指针
         3. 倒数第一个结点、倒数第二个结点依次等如何处理？反转链表
         4. 返回头节点head即可
      3. 不能改变节点值，必须真是的交换结点

      题解

      通过分析分部分处理，首先实现反转链表、寻找链表中间节点，然后切分链表，合并链表。

      合并链表的过程如何不理解的一定要自己画图。https://www.processon.com/

      链表类的题目画图最容易理解，不然容易绕晕！！！！

      本题考察的链表的知识点挺多的，特别好的一道题目。

      class Solution {
          public void reorderList(ListNode head) {
              ListNode mid = findMiddle(head);
              //表示第二段链表
              ListNode midNext = mid.next;
              //切断链表
              mid.next = null;
              //分成两段链表
              ListNode firstHead = head;
              ListNode secondHead = reverse(midNext);
              //合并两段链表
              while(secondHead != null){
                  ListNode next1 = firstHead.next;
                  ListNode next2 = secondHead.next;
                  firstHead.next = secondHead;
                  secondHead.next = next1;
                  firstHead = next1;
                  secondHead = next2;
              }
          }
          // 寻找链表中间节点
          private ListNode findMiddle(ListNode head) {
              ListNode slow = head;
              ListNode fast = head.next;
              while (fast != null && fast.next != null) {
                  slow = slow.next;
                  fast = fast.next.next;
              }
              return slow;
          }
          //反转链表
          public ListNode reverse(ListNode head){
              ListNode pre = null;
              ListNode cur = head;
              while(cur != null){
                  ListNode next = cur.next;
                  cur.next = pre;
                  pre = cur;
                  cur = next;
              }
              return pre;
          }
      }
      

      结果验证