#yyds干货盘点# 面试必刷TOP101:链表的奇偶重排

简述:

描述

给定一个单链表,请设定一个函数,将链表的奇数位节点和偶数位节点分别放在一起,重排后输出。

注意是节点的编号而非节点的数值。

数据范围:节点数量满足 #yyds干货盘点# 面试必刷TOP101:链表的奇偶重排插图,节点中的值都满足 #yyds干货盘点# 面试必刷TOP101:链表的奇偶重排插图1

要求:空间复杂度 #yyds干货盘点# 面试必刷TOP101:链表的奇偶重排插图2,时间复杂度 #yyds干货盘点# 面试必刷TOP101:链表的奇偶重排插图2

示例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

代码实现:

import java.util.*;
public class Solution {
public ListNode oddEvenList (ListNode head) {
//如果链表为空,不用重排
if(head == null)
return head;
//even开头指向第二个节点,可能为空
ListNode even = head.next;
//odd开头指向第一个节点
ListNode odd = head;
//指向even开头
ListNode evenhead = even;
while(even != null && even.next != null){
//odd连接even的后一个,即奇数位
odd.next = even.next;
//odd进入后一个奇数位
odd = odd.next;
//even连接后一个奇数的后一位,即偶数位
even.next = odd.next;
//even进入后一个偶数位
even = even.next;
}
//even整体接在odd后面
odd.next = evenhead;
return head;
}
}

文章来源于互联网:#yyds干货盘点# 面试必刷TOP101:链表的奇偶重排

THE END
分享
二维码