首页 > 代码库 > leetcode. Reorder List

leetcode. Reorder List

2024-08-06 11:59:36   215人阅读

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes‘ values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

1、通过双指针法得到链表中点，从而得到左右两个链表

2、将链表右半边逆序

3、合并两个链表

 1 void reorderList(ListNode *head)  2     { 3         if (head == NULL || head->next == NULL || head->next->next == NULL) 4             return; 5          6         ListNode *p, *q, *dummy = new ListNode(INT_MIN); 7         q = head; 8         p = q->next; 9         while (p != NULL)10         {11             q = q->next;12             p = p->next;13             if (p != NULL)14                 p = p->next;15         }16         17         dummy->next = q->next; // right half nodes18         q->next = NULL;19         q = head;   // left half nodes20         reverse(dummy);21         22         while (q != NULL)23         {24             p = dummy->next;25             dummy->next = p->next;26             p->next = q->next;27             q->next = p;28             q = q->next;29             q = q->next;30             if (dummy->next == NULL)31                 break;32         }33         delete dummy;34     }35     36     void reverse(ListNode *dummy)37     {38         ListNode *p = dummy, *q, *r;39         40         q = p->next;41         if (q == NULL)42             return;43         r = q->next;44         while (r != NULL)45         {46             q->next = p;47             p = q;48             q = r;49             r = r->next;50         }51         q->next = p;52         dummy->next->next = NULL;53         dummy->next = q;54     }

 

leetcode. Reorder List


联系
我们