当前位置： 面试刷题>> 奇偶链表 (经典算法题500道)
### 题目描述补充
**题目：奇偶链表**
给定一个单链表，将所有的奇数索引节点和偶数索引节点分别组合在一起。请注意，链表中节点的索引是从1开始的。
你需要以O(1)额外空间复杂度和O(n)的时间复杂度来重新排列这些节点。奇数索引节点和偶数索引节点应该分别形成两个链表，就原始链表中的顺序而言，第一个奇数索引节点应为第一个子链表的头节点，第一个偶数索引节点应为第二个子链表的头节点。在第二个子链表中，节点的相对顺序也应该与原始链表保持一致。
**示例 1**:
```
输入: 1->2->3->4->5->NULL
输出: 1->3->5->NULL, 2->4->NULL
```
**示例 2**:
```
输入: 2->1->3->5->6->4->7->NULL
输出: 2->3->6->7->NULL, 1->5->4->NULL
```
### PHP 示例代码
```php
class ListNode {
public $val = 0;
public $next = null;
function __construct($val = 0, $next = null) {
$this->val = $val;
$this->next = $next;
}
}
function oddEvenList($head) {
if (!$head || !$head->next) {
return $head;
}
$odd = $head;
$even = $head->next;
$evenHead = $even;
while ($even && $even->next) {
$odd->next = $even->next;
$odd = $odd->next;
$even->next = $odd->next;
$even = $even->next;
}
$odd->next = $evenHead;
return $head;
}
// 示例用法
$head = new ListNode(1);
$head->next = new ListNode(2);
$head->next->next = new ListNode(3);
$head->next->next->next = new ListNode(4);
$head->next->next->next->next = new ListNode(5);
$oddHead = oddEvenList($head);
// 这里需要额外的逻辑来打印或验证结果，因为PHP不直接支持打印链表
```
### Python 示例代码
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def oddEvenList(head):
if not head or not head.next:
return head
odd = head
even = head.next
evenHead = even
while even and even.next:
odd.next = even.next
odd = odd.next
even.next = odd.next
even = even.next
odd.next = evenHead
return head
# 示例用法
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
oddHead = oddEvenList(head)
# 这里可以添加额外的逻辑来打印或验证结果
```
### JavaScript 示例代码
```javascript
function ListNode(val, next) {
this.val = (val===undefined ? 0 : val)
this.next = (next===undefined ? null : next)
}
function oddEvenList(head) {
if (!head || !head.next) {
return head;
}
let odd = head;
let even = head.next;
let evenHead = even;
while (even && even.next) {
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
}
// 示例用法
let head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);
let oddHead = oddEvenList(head);
// 这里可以添加额外的逻辑来打印或验证结果
```
**码小课网站中有更多相关内容分享给大家学习**，包括链表操作、算法设计、数据结构等深入内容，帮助大家提升编程技能。