Relocate List

发表于 | 分类于

根据左右半区重新排列链表

题目描述：

给定一个链表的头结点，其长度为N。如果长度为偶数的情况下，认为前N/2为左半区，后N/2为右半区；如果N为奇数，则认为前N/2为左半区，后N/2+1为右半区。根据如下例子中规则重新排列链表。

例子：

假设原链表为1->2->3->4->5->NULL,调整后为1->3->2->4->5->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
#include "ListNode.h"
class relocateList1{
public:
    ListNode* relocateList(ListNode* head){
        if (head == NULL || head->next == NULL)
            return head;
        ListNode* right = head->next;
        ListNode* left = head;
        while(right->next != NULL && right->next->next != NULL){
            left = left->next;
            right = right->next->next;
        }                  // 找到链表的中间节点。
        right = left->next;
        left->next = NULL; // 断开左右半区的连接
        left = head;
        ListNode* next1 = NULL;
        ListNode* next2 = NULL;
        while(left->next != NULL){
            next1 = left->next;  //记录左当前节点的下一个节点
            next2 = right->next; //记录右当前节点的下一个节点
            left->next = right;
            right->next = next1; // 重新调整链表的指向
            left = next1;
            right = next2;       //进行下一次的遍历
        }
        left->next = right;
        return head;
    }
};