|
给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。 请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。 示例 1: 输入: 1->2->3->4->5->NULL 输出: 1->3->5->2->4->NULL
示例 2: 输入: 2->1->3->5->6->4->7->NULL 输出: 2->3->6->7->1->5->4->NULL
说明: 这题是让把链表的奇数节点和偶数节点单独分开，我们自然想到的是把奇数节点串到一起，我们称之为奇数链表，偶数节点串到一起，我们称之为偶数链表。最后再把偶数链表挂到奇数链表的后面即可。如下图所示 
串完之后分开来看就是下面这样 
注意这里需要使用几个变量，分别记录奇数链表的头节点和尾节点，偶数链表的头节点和尾节点。关于链表的题直接看不太容易理解，画图是解链表相关题的最好方式。我们来看下代码 public ListNode oddEvenList(ListNode head) {
if (head == null || head.next == null)
return head;
//奇数链表的头节点
ListNode oddHead = head;
//奇数链表的当前节点
ListNode oddCur = oddHead;
//偶数链表的头节点
ListNode evenHead = head.next;
//偶数链表的当前节点
ListNode evenCur = evenHead;
while (evenCur != null && evenCur.next != null) {
//奇数节点串一起
oddCur.next = oddCur.next.next;
//偶数节点串一起
evenCur.next = evenCur.next.next;
//奇偶指针往后移
oddCur = oddCur.next;
evenCur = evenCur.next;
}
//最后偶数链表和奇数链表需要串在一起
oddCur.next = evenHead;
return oddHead;
}
|
