LeetCode 328. 奇偶链表
原题链接
中等
作者:
bruce
,
2020-12-25 15:59:18
,
所有人可见
,
阅读 319
/**
* 方法 1,两个指针,一个是指向偶数节点,一个指向奇数节点,把偶数节点后面的奇数节点提前到第一个奇数的后面。
* 然后两个指针各前进一步即可
* */
ListNode *oddEvenList(ListNode *head)
{
if (head == nullptr || head->next == nullptr)
return head;
ListNode *cur = head->next;
ListNode *pre = head;
while (cur && cur->next)
{
ListNode *temp = pre->next;
pre->next = cur->next;
cur->next = cur->next->next;
pre->next->next = temp;
cur = cur->next;
pre = pre->next;
}
return head;
}
/**
* 方法 2,使用两个指针分别保存奇数和偶数下标的链表
* 最后把这两个链表合并即可,注意在偶数链表保存的时候要记录偶数的头指针
*/
ListNode *oddEvenList(ListNode *head)
{
if (!head || !head->next)
return head;
ListNode *odd = head, *evn = head->next, *evnhead = evn;
ListNode *cur = head;
while (odd->next && evn->next)
{
odd->next = evn->next;
odd = odd->next;
evn->next = odd->next;
evn = evn->next;
}
odd->next = evnhead;
return head;
}