文章目錄
- 題目
- 解題思維1：
- 代碼
- 附圖
- 解題思維二
- 來看，我們創建兩個 節點 參考 odd(奇數)等于 head（第一個節點的地址），第二個節點 為 even(偶數)，
- 因為我們是直接在原鏈表上開刀，所以 odd不用在創建一個替身去鏈接后面的節點（原鏈表有head，而odd==head，讓 odd名副其實的去鏈接后面的節點），但是 even 原鏈表中可沒有具體的參考記住它的地址，所以我們需要為 even 創建一個替身去鏈接節點，
- 現在我們的前期準備已完成，現在我們要思考一個問題，原鏈表的頭節點為奇數，頭節點（head.next）的下一個節點為偶數（even），那么 偶數節點下一個節點就是奇數節點(evenCur.next),我們就將其接入 奇數節點的后面（odd.next)，然后，該節點下一個節點不就偶數節點了！我們再將其接入 偶數節點的后面(even.next)，
- 最后只需要拼接就行了
- 代碼如下
題目
?
解題思維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; }
* }
*/
class Solution {
public ListNode oddEvenList(ListNode head) {
if(head == null){
return null;
}
ListNode evenLinked = new ListNode();// 偶數鏈表頭節點
ListNode evenCur = evenLinked;// 偶數鏈表頭節點的替身
ListNode oddLinked = new ListNode();// 奇數鏈表頭節點
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)，
?
最后只需要拼接就行了
代碼如下
class Solution {
public ListNode oddEvenList(ListNode head) {
if(head == null){
return null;
}
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;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/396185.html
標籤：java