Reorder List

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. class Solution {
  2. public:
  3.     void reorderList(ListNode *head) {
  4.         if(head == NULL || head->next == NULL) {
  5.             return;
  6.         }
  8.         ListNode* fast = head;
  9.         ListNode* slow = head;
  12.         //快慢指针切分链表
  13.         while(fast->next != NULL && fast->next->next != NULL){
  14.             fast = fast->next->next;
  15.             slow = slow->next;
  16.         }
  18.         fast = slow->next;
  19.         slow->next = NULL;
  21.         //翻转右半部分
  22.         ListNode dummy(0);
  23.         while(fast) {
  24.             ListNode* n = dummy.next;
  25.             dummy.next = fast;
  26.             ListNode* nn = fast->next;
  27.             fast->next = n;
  28.             fast = nn;
  29.         }
  31.         slow = head;
  32.         fast = dummy.next;
  34.         //依次合并
  35.         while(slow) {
  36.             if(fast != NULL) {
  37.                 ListNode* n = slow->next;
  38.                 slow->next = fast;
  39.                 ListNode* nn = fast->next;
  40.                 fast->next = n;
  41.                 fast = nn;
  42.                 slow = n;
  43.             } else {
  44.                 break;
  45.             }
  46.         }
  47.     }
  48. };