牛客网高频算法题系列-BM14-链表的奇偶重排
题目形容
给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点别离放在一起，重排后输入。
留神是节点的编号而非节点的数值。原题目见：BM14 链表的奇偶重排
解法一：链表遍历（应用额定空间）
首先，判断如果链表为空或者只有1或2个结点，不必重排，间接返回原链表。
否则，应用2个list额定记录奇数和偶数位的结点，处理过程如下：
- 遍历链表，别离将奇数和偶数位的结点值放到不同的list中；
- 依照奇数位在前、偶数位在后的程序，将2个list中的值重组成新的链表即为重排后的链表，返回之。
解法二：双指针法
同样的，首先要判断如果链表为空或者只有1或2个结点，不必重排，间接返回原链表。
否则，应用odd和even结点别离指向链表的第一个（奇数）和第二个（偶数）结点，而后遍历链表，将奇数位的结点和偶数位的结点别离连接起来，最初，将偶数位的放到奇数位的链表前面，即为重排后的链表。
代码
import java.util.ArrayList;import java.util.List;public class Bm014 { /** * 应用额定的空间 * * @param head ListNode类 * @return ListNode类 */ public static ListNode oddEvenList(ListNode head) { // 如果链表为空或者只有1或2个结点，不必重排 if (head == null || head.next == null || head.next.next == null) { return head; } // 奇数结点 List<Integer> odds = new ArrayList<>(); // 偶数结点 List<Integer> evens = new ArrayList<>(); int i = 1; while (head != null) { if (i % 2 == 1) { odds.add(head.val); } else { evens.add(head.val); } head = head.next; i++; } ListNode newHead = new ListNode(-1), cur = newHead; for (Integer val : odds) { cur.next = new ListNode(val); cur = cur.next; } for (Integer val : evens) { cur.next = new ListNode(val); cur = cur.next; } return newHead.next; } /** * 双指针法 * * @param head * @return */ public static ListNode oddEvenList2(ListNode head) { // 如果链表为空或者只有1或2个结点，不必重排 if (head == null || head.next == null || head.next.next == null) { return head; } // 奇数结点 ListNode odd = head; // 偶数结点，偶数链表头 ListNode evenHead = head.next, even = evenHead; while (even != null && even.next != null) { // odd连贯奇数位结点 odd.next = even.next; odd = odd.next; // even连贯偶数位结点 even.next = odd.next; even = even.next; } // 最初将odd链表的最初一个结点指向even链表的表头 odd.next = evenHead; return head; } public static void main(String[] args) { ListNode head = ListNode.testCase5(); System.out.println("原链表为"); ListNode.print(head); System.out.println("重排后的链表为"); ListNode.print(oddEvenList(head)); ListNode.print(oddEvenList2(head)); }}$1.01^{365} ≈ 37.7834343329$
$0.99^{365} ≈ 0.02551796445$
置信保持的力量！