LeetCode - 328 - 奇偶链表 - java - 一种思维，两种解法

文章目录

题目

解题思维1：

创建里两个头节点，分别代表 奇数(odd)链表的头节点， 偶数(even)链表的头节点。
再分别 这两个节点创建一个替身，用来连接 对应各自属性的节点。
至于题目的 head，就不用创建替身，直接用head 去遍历链表就行了。
需要注意的是 链表是没有下标这个东西的，所以我们需要定义整形变量 n 等于1，因为题目说链表的第一个节点为奇数，第二个节点为偶数。
最后将 偶数链表 和 奇数链表 拼接起来就可以了。

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */classSolution{publicListNodeoddEvenList(ListNode head){if(head ==null){returnnull;}ListNode evenLinked =newListNode();// 偶数链表头节点ListNode evenCur = evenLinked;// 偶数链表头节点的替身ListNode oddLinked =newListNode();// 奇数链表头节点ListNode oddCur = oddLinked;// 奇数链表头节点替身int n  =1;// 用来表示 现在 head 指向的是第几个节点，方便我们来判断个数的奇偶性while(head!=null){if(n %2!=1){//判断 第 n 个节点， n 是否偶数，是就接入偶数链表
                evenCur.next = head;
                evenCur = evenCur.next;}else{//  第 n 个节点， n 既然不是偶数，那就是奇数了，就接入奇数链表
                oddCur.next = head;
                oddCur = oddCur.next;}
            head = head.next;// head 继续遍历原链表 
            n++;// 此时 head 指向了 第 n +1 个节点 }//因为偶数位置的节点放在右边的，所以需要注意偶数链表最后一个节点的next，需要置为null。防止造成环！
        evenCur.next =null;
        oddCur.next = evenLinked.next;// 将奇数链表 和 偶数链表结合，其结果就是我们想要的return oddLinked.next;// 在合并后，奇数链表的节点是前面的，所以我们返回 奇数链表的头节点的next。// 因为我们奇数链表是一个带头的链表，所有头节点的值是不重要的！}}

附图

解题思维二

与上题相同的是我们还是用了将链表分割成两部分，最后合并。
不同的是，我们是直接在原链表身上直接开刀。
首先我们知道 这题的奇偶性是以 第 n 个节点，n 的奇偶性决定的。
要求 第 n 节点的 n 为奇数的放在链表左边，为偶数统一放在链表的右边。

来看，我们创建两个 节点 引用 odd(奇数)等于 head（第一个节点的地址），第二个节点 为 even(偶数)。

因为我们是直接在原链表上开刀，所以 odd不用在创建一个替身去链接后面的节点（原链表有head，而odd==head，让 odd名副其实的去链接后面的节点），但是 even 原链表中可没有具体的引用记住它的地址，所以我们需要为 even 创建一个替身去链接节点。

现在我们的前期准备已完成，现在我们要思考一个问题，原链表的头节点为奇数，头节点（head.next）的下一个节点为偶数（even），那么 偶数节点下一个节点就是奇数节点(evenCur.next),我们就将其接入 奇数节点的后面（odd.next)，然后，该节点下一个节点不就偶数节点了！我们再将其接入 偶数节点的后面(even.next)。

最后只需要拼接就行了

代码如下

classSolution{publicListNodeoddEvenList(ListNode head){if(head ==null){returnnull;}ListNode odd = head;ListNode even = head.next;ListNode evenCur = even;while(evenCur !=null&& evenCur.next !=null){
            odd.next = evenCur.next;
            odd = odd.next;
            evenCur.next = odd.next;
            evenCur = evenCur.next;}
        odd.next = even;return head;}}