给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点分别放在一起，重排后输出。
注意是节点的编号而非节点的数值。
数据范围：节点数量满足 
，节点中的值都满足 
要求：空间复杂度 )
，时间复杂度
[编程题]链表的奇偶重排
- 热度指数：115160 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
示例1
输入
{1,2,3,4,5,6}输出
{1,3,5,2,4,6}
说明
1->2->3->4->5->6->NULL重排后为1->3->5->2->4->6->NULL
示例2
输入
{1,4,6,3,7}输出
{1,6,7,4,3}
说明
1->4->6->3->7->NULL重排后为1->6->7->4->3->NULL
奇数位节点有1,6,7，偶数位节点有4,3。重排后为1,6,7,4,3
备注:
链表长度不大于200000。每个数范围均在int内。
说明：本题目包含复杂数据结构ListNode，点此查看相关信息
画图过一遍就懂，简单明了。
public ListNode oddEvenList (ListNode head) {
// write code here
if(head == null || head.next == null) return head;
ListNode evenHead = head.next;
ListNode odd = head,even = head.next;
while(even != null && even.next != null){
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
}
发表于 2020-09-23 16:28:44
回复(9)
如果有奇数个链表，记得把偶数节点链表的最后一个节点的next属性设置为null，否则会出现环形链表然后报错，debug了好久踩了这个坑
发表于 2022-09-02 15:42:25
回复(1)
public ListNode oddEvenList(ListNode head) {
if(head==null) return head;
//无需对头节点做操作 不用dummyHead
//奇链表头位于head 偶链表头位于head.next
ListNode oddHead = head,evenHead = head.next;
ListNode odd = oddHead,even = evenHead;
//终止条件：因为even走在前面 一定先终止 所以判断条件就是它
//节点总数为偶数个时 even.next为null
//节点总数为奇数个时： even==null 这俩条件触发一个就跳出循环
while (even!=null&&even.next!=null){
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
//奇偶链表拼接
odd.next = evenHead;
return head;
}
发表于 2021-03-15 19:11:26
回复(1)
class Solution:
def oddEvenList(self , head: ListNode) -> ListNode:
# write code here
evenHead = head.next # 偶数的第一个
odd = head # 奇数
even = head.next # 偶数
while even and even.next:
odd.next = even.next # 奇数指向奇数
odd = odd.next
even.next = odd.next # 偶数指向偶数
even = even.next
odd.next = evenHead # 奇数最后一个指向偶数第一个
return head
发表于 2022-04-25 23:04:51
回复(3)
双指针
function oddEvenList( head ) {
// write code here
if(!head) return head
let odd = head ///扫描奇链节点
let even = head.next ///扫描偶链节点
let evenHead = even //保存偶数链的节点
while(even&&even.next){
odd.next = odd.next.next //指向下一个奇数节点
even.next = even.next.next //指向下一个奇数节点
odd = odd.next //odd推进到下一个奇数节点
even = even.next //even推进到下一个偶数节点
}
odd.next = evenHead //奇数链连上偶数链
return head
}
发表于 2020-12-17 16:32:43
回复(2)
开始没看题目以为按值来奇偶重组，把问题想复杂了……
按值：
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
ListNode* oddEvenList(ListNode* head) {
// write code here
ListNode* odd = head, *even = head, *curr, *pre;
if (head->val % 2 == 0) {
while (odd && odd->val % 2 == 0) {
odd = odd->next;
}
pre = odd;
curr = odd->next;
} else {
while (even && even->val % 2 == 1) {
even = even->next;
}
pre = even;
curr = even->next;
}
while (curr) {
if (curr->val % 2 == 1) {
if (pre == even) {
pre->next = curr->next;
curr->next = odd->next;
odd->next = curr;
curr = pre->next;
odd = odd->next;
}else {
odd = odd->next;
pre = pre->next;
curr = curr->next;
}
} else {
if (pre == odd) {
pre->next = curr->next;
curr->next = even->next;
even->next = curr;
curr = pre->next;
even = even->next;
}else {
even = even->next;
pre = pre->next;
curr = curr->next;
}
}
}
return head;
}
}; 按编号： /**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
ListNode* oddEvenList(ListNode* head) {
// write code here
if(head==nullptr) return nullptr;
ListNode *evenhead=head->next, *odd=head, *even=evenhead;
while (even&&even->next) {
odd->next = even->next;
even->next = even->next->next;
odd = odd->next;
even = even->next;
}
odd->next = evenhead;
return head;
}
};
发表于 2023-09-02 14:08:17
回复(0)
public ListNode oddEvenList (ListNode head) {
// write code here
if (head==null)return head;
ListNode ji=head;
ListNode ou=head.next;
ListNode jiCur=ji;
ListNode ouCur=ou;
//分别建立奇链表和偶链表，然后将两个链表连起来
while (jiCur!=null&&ouCur!=null&&jiCur.next!=null&&ouCur.next!=null){
jiCur.next=jiCur.next.next;
jiCur=jiCur.next;
ouCur.next=ouCur.next.next;
ouCur=ouCur.next;
}
jiCur.next=ou;
return ji;
}
发表于 2021-07-15 17:15:06
回复(0)
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param head ListNode类
* @return ListNode类
*/
public ListNode oddEvenList (ListNode head) {
// write code here
//假设第一个节点为奇数，所以在代码中体现出来最后一个奇数节点必定指向第一个偶数节点，
//原地算法：使空间复杂度为常数。定义odd,even,evenHead.每次都向前推进，只不过奇数找奇数，偶数找偶数。
if(head == null) return null;
ListNode odd = head,even = odd.next,evenHead = even;
while(even != null && even.next != null ){
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
}
}
发表于 2020-11-04 11:08:24
回复(0)
第二种方法来了， 放到两个数组里面，再加会链表里去
public ListNode oddEvenList (ListNode head) {
// write code hereListNode cur = head;
ArrayList<Integer> even = new ArrayList<Integer>();
ArrayList<Integer> odd = new ArrayList<Integer>();
int i = 0;
while (cur != null) {
if (i % 2 == 0) {
even.add(cur.val);
} else {
odd.add(cur.val);
}
cur = cur.next;
++i;
}
cur = head;
for (int j = 0; j < even.size();j++) {
cur.val = even.get(j);
cur = cur.next;
}
for (int K = 0; K < odd.size();K++) {
cur.val = odd.get(K);
cur = cur.next;
}
return head;
}
发表于 2022-04-26 14:34:34
回复(1)
果然还是别人题解更强
原来的思路按照奇偶节点拆分为两个链表，然后在进行合并，代码显得很长。。。，而且要新开节点
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
ListNode* oddEvenList(ListNode* head) {
// write code here
// if(head == NULL) return head;
// ListNode *oldhead = head, *evenhead = head->next;
// ListNode *oldp = head, *evenp = evenhead;
// while(evenp != NULL && evenp->next != NULL){
// oldp->next = evenp->next;
// oldp = oldp->next;
// evenp->next = oldp->next;
// evenp = evenp->next;
// }
// oldp->next = evenhead;
// return head;
if(head == NULL) return head;
ListNode *ohead = new ListNode(0), *ehead = new ListNode(0);
ListNode *p = head, *p1 = ohead, *p2 = ehead;
int cnt = 1;
while(p != NULL){
ListNode *tmp = p->next;
if(cnt%2 == 1){
p->next = p1->next;
p1->next = p;
p1 = p1->next;
}
else{
p->next = p2->next;
p2->next = p;
p2 = p2->next;
}
p = tmp;
++cnt;
}
p1->next = ehead->next;
ehead->next = NULL;
free(ehead);
ohead->next = NULL;
free(ohead);
return head;
}
};
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
ListNode* oddEvenList(ListNode* head) {
// write code here
if(head == NULL) return head;
ListNode *oldhead = head, *evenhead = head->next;
ListNode *oldp = head, *evenp = evenhead;
while(evenp != NULL && evenp->next != NULL){
oldp->next = evenp->next;
oldp = oldp->next;
evenp->next = oldp->next;
evenp = evenp->next;
}
oldp->next = evenhead;
return head;
// if(head == NULL) return head;
// ListNode *ohead = new ListNode(0), *ehead = new ListNode(0);
// ListNode *p = head, *p1 = ohead, *p2 = ehead;
// int cnt = 1;
// while(p != NULL){
// ListNode *tmp = p->next;
// if(cnt%2 == 1){
// p->next = p1->next;
// p1->next = p;
// p1 = p1->next;
// }
// else{
// p->next = p2->next;
// p2->next = p;
// p2 = p2->next;
// }
// p = tmp;
// ++cnt;
// }
// p1->next = ehead->next;
// ehead->next = NULL;
// free(ehead);
// ohead->next = NULL;
// free(ohead);
// return head;
}
};
编辑于 2021-05-26 14:39:07
回复(0)
解题思路：使用标记每两次，跳过一个节点，并将其单独加到偶数节点后面，最后把偶数链放到奇数链后面
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param head ListNode类
* @return ListNode类
*/
public ListNode oddEvenList (ListNode head) {
// write code here
int flag=0;
ListNode odd=new ListNode(0);
ListNode node=odd;
ListNode pre=head;
ListNode cur=head;
while(cur!=null){
if(flag%2==1){
pre.next=cur.next;
ListNode temp=cur;
temp.next=null;
odd.next=temp;
odd=odd.next;
cur=pre;
}
pre=cur;
cur=cur.next;
flag++;
}
pre.next=node.next;
return head;
}
}
发表于 2021-03-16 14:09:17
回复(0)
将链表拆分为两个链表: 奇数位链表、偶数位链表，然后拼接到一起返回。
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param head ListNode类
* @return ListNode类
*/
ListNode* oddEvenList(ListNode* head) {
// 空链表或者只有一个结点
if(!head || !head->next) {
return head;
}
ListNode *oddHead = new ListNode(0), *everHead = new ListNode(0);
ListNode *odd = oddHead, *ever = everHead;
int id = 0;
ListNode *p = head;
while(p) {
if((++id) % 2 == 0) {
odd->next = p;
odd = p;
}
else {
ever->next = p;
ever = p;
}
p = p->next;
}
ever->next = NULL;
odd->next = NULL;
ever->next = oddHead->next;
return everHead->next;
}
};
发表于 2020-10-02 15:59:00
回复(0)
# class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param head ListNode类 # @return ListNode类 # class Solution: def oddEvenList(self , head: ListNode) -> ListNode: # write code here p = head if p is None: return head head1,head2 = ListNode(-1),ListNode(-1) q1,q2 = head1,head2 ans = 1 while p: if ans % 2 == 0: q2.next = p q2 = p elif ans % 2 != 0: q1.next = p q1 = p p = p.next ans += 1 if q1.next == q2: q1.next = head2.next q2.next = None elif q2.next == q1: q1.next = head2.next q2.next = None return head1.next
定义两个新的链表，一个用来存储奇数一个存储偶数下标，用一个指针p去遍历原链表最后判断一下结束时候2个指针的连接关系即可
发表于 2024-10-15 19:18:28
回复(0)
struct ListNode* oddEvenList(struct ListNode* head ) {
if(head==NULL)
{
return NULL;
}
if(head->next==NULL||head->next->next==NULL)
{
return head;
}
struct ListNode* odd=head;
struct ListNode* even=head->next;
struct ListNode* node=head->next;
while(even!=NULL&&even->next!=NULL)
{
struct ListNode* next = even->next;
odd->next=even->next;
even->next=next->next;
odd=odd->next;
even=even->next;
}
odd->next=node;
return head;
}
编辑于 2024-04-13 23:01:32
回复(1)
struct ListNode* oddEvenList(struct ListNode* head ) {
if(head==NULL || head->next==NULL)return head;
struct ListNode* odd=head,*even=head->next;
struct ListNode* p=head->next->next,*q=even;
int cnt=0;
while(p)
{
cnt++;
if(cnt%2==1)
{
odd->next=p;
odd=p;
}
else {
even->next=p;
even=p;
}
p=p->next;
}
even->next=NULL;
odd->next=q;
return head;
} 时间复杂on，空间复杂度o1
发表于 2023-10-02 18:29:18
回复(0)
# class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param head ListNode类 # @return ListNode类 # class Solution: def oddEvenList(self , head: ListNode) -> ListNode: # write code here if not head: return None oddHead = head.next # 奇偶指针 left, right = head, head.next while right and right.next: left.next = right.next left = left.next right.next = left.next right = right.next left.next = oddHead return head
发表于 2023-09-05 10:13:10
回复(0)
class Solution: def oddEvenList(self , head: ListNode) -> ListNode: # write code here odd_head = ListNode(0) even_head = ListNode(0) p_odd = odd_head p_even = even_head flag = True p = head while p: if flag: p_odd.next = p p_odd = p else: p_even.next = p p_even = p p = p.next flag = not flag p_odd.next = even_head.next p_even.next = None return odd_head.next
发表于 2023-07-20 23:05:18
回复(0)
struct ListNode* oddEvenList(struct ListNode* head ) {
// write code here
int s[100000] = {0};
int i = 0;
int j;
struct ListNode *p = head;
//如果head为空，直接返回
if (head == NULL) return head;
//先将奇数号节点的val赋给s
while (p) {
s[i++] = p->val;
p = p->next;
if (p) {
p = p->next;
}
}
//将偶数号节点的val赋给s
//p先指向第一个偶数节点
p = head->next;
while (p) {
s[i++] = p->val; //i在原有基础上赋值
p = p->next;
if (p) {
p = p->next;
}
}
//将s中的值一一重新赋给head
p = head;
i = 0;
while (p) {
p->val = s[i++];
p = p->next;
}
return head;
}
发表于 2023-03-20 14:11:44
回复(0)
public ListNode oddEvenList (ListNode head) {
//空 一个 两个节点 直接返回
if(head==null||head.next==null||head.next.next==null)
return head;
ListNode snd = head.next;//偶数头
ListNode cur1 = head;//处理奇数节点
ListNode cur2 = snd;//处理偶数节点
while(cur1!=null&&cur2!=null){//奇数连接、偶数连接
cur1.next = cur2.next;
if(cur2.next==null) break;
cur1 = cur2.next;
cur2.next = cur1.next;
cur2 = cur1.next;
}
cur1.next = snd;//奇数尾连接偶数头
return head;
}
发表于 2023-03-12 19:33:45
回复(0)
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
ListNode* oddEvenList(ListNode* head) {
// write code here
if(head == NULL || head -> next == NULL) return head;
ListNode *p = head, *q = head -> next;
int cnt = 0;
while(p)
{
cnt++;
p = p -> next;
}
p = head;
if(cnt % 2 == 0)
{
while(q -> next)
{
ListNode *r = q -> next;
q -> next = r -> next;
r -> next = p -> next;
p -> next = r;
p = r;
q = q -> next;
}
}
else
{
while(q)
{
ListNode *r = q -> next;
q -> next = r -> next;
r -> next = p -> next;
p -> next = r;
p = r;
q = q -> next;
}
}
return head;
}
};
发表于 2023-02-10 12:33:44
回复(0)
问题信息
通过挑战的用户
查看代码-
2023-02-16 18:14:55 -
2022-11-29 22:42:59
-
2022-11-02 23:59:12 -
2022-09-22 18:31:08 -
2022-09-18 00:20:36
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
