创建里两个头节点,分别代表 奇数(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 为奇数的放在链表左边,为偶数统一放在链表的右边。
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://blog.csdn.net/DarkAndGrey/article/details/122199667
内容来源于网络,如有侵权,请联系作者删除!