牛客网高频算法题系列-BM14-链表的奇偶重排

题目描述

给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点分别放在一起，重排后输出。
注意是节点的编号而非节点的数值。

原题目见：BM14 链表的奇偶重排

解法一：链表遍历（使用额外空间）

首先，判断如果链表为空或者只有1或2个结点，不用重排，直接返回原链表。

否则，使用2个list额外记录奇数和偶数位的结点，处理过程如下：

  • 遍历链表，分别将奇数和偶数位的结点值放到不同的list中；
  • 按照奇数位在前、偶数位在后的顺序，将2个list中的值重组成新的链表即为重排后的链表，返回之。

解法二：双指针法

同样的，首先要判断如果链表为空或者只有1或2个结点，不用重排，直接返回原链表。

否则，使用odd和even结点分别指向链表的第一个（奇数）和第二个（偶数）结点，然后遍历链表，将奇数位的结点和偶数位的结点分别连接起来，最后，将偶数位的放到奇数位的链表后面，即为重排后的链表。

代码

  1. import java.util.ArrayList;
  2. import java.util.List;
  4. public class Bm014 {
  5.     /**
  6.      * 使用额外的空间
  7.      *
  8.      * @param head ListNode类
  9.      * @return ListNode类
  10.      */
  11.     public static ListNode oddEvenList(ListNode head) {
  12.         // 如果链表为空或者只有1或2个结点，不用重排
  13.         if (head == null || head.next == null || head.next.next == null) {
  14.             return head;
  15.         }
  16.         // 奇数结点
  17.         List<Integer> odds = new ArrayList<>();
  18.         // 偶数结点
  19.         List<Integer> evens = new ArrayList<>();
  21.         int i = 1;
  22.         while (head != null) {
  23.             if (i % 2 == 1) {
  24.                 odds.add(head.val);
  25.             } else {
  26.                 evens.add(head.val);
  27.             }
  28.             head = head.next;
  29.             i++;
  30.         }
  32.         ListNode newHead = new ListNode(-1), cur = newHead;
  33.         for (Integer val : odds) {
  34.             cur.next = new ListNode(val);
  35.             cur = cur.next;
  36.         }
  37.         for (Integer val : evens) {
  38.             cur.next = new ListNode(val);
  39.             cur = cur.next;
  40.         }
  42.         return newHead.next;
  43.     }
  45.     /**
  46.      * 双指针法
  47.      *
  48.      * @param head
  49.      * @return
  50.      */
  51.     public static ListNode oddEvenList2(ListNode head) {
  52.         // 如果链表为空或者只有1或2个结点，不用重排
  53.         if (head == null || head.next == null || head.next.next == null) {
  54.             return head;
  55.         }
  57.         // 奇数结点
  58.         ListNode odd = head;
  59.         // 偶数结点，偶数链表头
  60.         ListNode evenHead = head.next, even = evenHead;
  61.         while (even != null && even.next != null) {
  62.             // odd连接奇数位结点
  63.             odd.next = even.next;
  64.             odd = odd.next;
  65.             // even连接偶数位结点
  66.             even.next = odd.next;
  67.             even = even.next;
  68.         }
  69.         // 最后将odd链表的最后一个结点指向even链表的表头
  70.         odd.next = evenHead;
  71.         return head;
  72.     }
  74.     public static void main(String[] args) {
  75.         ListNode head = ListNode.testCase5();
  76.         System.out.println("原链表为");
  77.         ListNode.print(head);
  79.         System.out.println("重排后的链表为");
  80.         ListNode.print(oddEvenList(head));
  81.         ListNode.print(oddEvenList2(head));
  82.     }
  83. }

牛客网高频算法题系列-BM14-链表的奇偶重排 - 图1
牛客网高频算法题系列-BM14-链表的奇偶重排 - 图2
相信坚持的力量！