143. Reorder List

发表于 | 分类于

每日一题 2019 - 05 - 09

题目：

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

You may not modify the values in the list’s nodes, only nodes itself may be changed.

Example 1:

1
Given 1->2->3->4, reorder it to 1->4->2->3.

Example 2:

1
Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

解法：

这个题让把链表按照题目要求的方式进行重新排序，可以把排序的结果看作是两个过程的结合：

  • 先找到链表的中间位置把后一部分翻转
  • 把后一部分倒序插入链表之中

所以就需要使用两个指针完成查找工作，一个快指针用于遍历整个链表，一个慢指针用来找到链表中间的位置，随后，每一次从链表后半部分开始往前插入，这时候可以找到对应的插入关系，也即当前待插入的位置与即将被移动的位置之和为链表长度的一半减1，所以根据这个关系就能很好的完成相应的插入操作；

最后还要注意把插入完成后的链表末尾位置指向 NULL；

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        ListNode* p = head ;
        ListNode* q = head ;
        ListNode* temp = head ;
        int count = 0 ;
        if(head == NULL)
        {
            return ;
        }
        while(p->next)
        {
            p = p -> next ;
            count ++;
            if(count % 2 == 1)
            {
                temp = temp -> next ;
            }
        }
        count /= 2 ;
        for(int i = 0 ; i < count ; i ++)
        {
            for(int j = 0 ; j < count - i - 1 ; j ++ )
            {
                q = q -> next ;
            }
            //链表结点的拼接步骤
            p = temp -> next ;
            temp -> next = p -> next ;
            p -> next = q -> next ;
            q -> next = p ;
            q = head ; 
        }
        temp -> next = NULL ;
    }
};
0%
undefined