题目描述
一个包含$n$个元素的线性链表 $L=(a1,a2,…,an−2,an−1,an)$
现在要对其中的结点进行重新排序,得到一个新链表 $ L′=(a1,an,a2,an−1,a3,an−2…)$
样例
输入:1->2->3->4->5
输出:1->5->2->4->3
思路1:反转链表+合并链表
即先找到断开的位置,随后将该链表分为前后两个,将后者反转;随后再合并两个链表
代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void rearrangedList(ListNode* head) {
if (head -> next == NULL)//判空
return;
//(1)计元素总数
int sum = 0;
ListNode *a = head;
while (a)
{
sum++;
a = a -> next;
}
//(2)断开链表
ListNode * tmp = head;
ListNode * prev = head;
ListNode * rear;//存放被断开的后面的链表的第一个元素
int cnt = 0;
while (tmp)
{
prev = tmp;
tmp = tmp -> next;
cnt++;
if ((sum % 2 == 1 && cnt == sum / 2 + 1) || (sum % 2 == 0 && cnt == sum / 2))
{
rear = tmp;
prev -> next = NULL;//此处就实现了链表的断开
tmp = NULL;
}
}
//(3)将后面的链表进行反转,此时rear指向后面链表的第一个元素
ListNode * c = rear -> next;
rear -> next = NULL;
while (c != NULL)
{
ListNode * tmp = c -> next;
c -> next = rear;
rear = c;
c = tmp;
}
//(4)此时rear是后面的链表的头结点,然后遍历两个链表实现间隔插入
ListNode *front = head;
while (rear)
{
ListNode * tmp_front = front -> next;
ListNode * tmp_rear = rear -> next;
rear -> next = tmp_front;
front -> next = rear;
rear = tmp_rear;
front = tmp_front;
}
}
};
思路2:断开原链表,再将前者链表间隔地插入新结点
(这样做的空间复杂度不是O(1))
(1)先遍历一遍得到总元素的数量n;
(2)随后(n/2向上取整)之后的元素就是即将要删除的;
(3)随后从(n/2向上取整)之后断开该链表,并把被断开的后面的链表的值放入一个数组中
(4)从该数组的最后一位以及已前者链表的头结点开始,依次创建结点并分别间隔插入
代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void rearrangedList(ListNode* head) {
//(1)计元素总数
int sum = 0;
ListNode *a = head;
while (a)
{
sum++;
a = a -> next;
}
//(2)把链表从n/2向上取整处断开,并将之后的结点存入到数组中
int Node_val[sum];
ListNode * b = head;
ListNode * prev = head;//prev始终指向b的前驱
int cnt = 0;//记录什么时候可以断开
int tmp = 0;
while (b)
{
prev = b;
b = b -> next;
cnt++;
if ((sum % 2 == 1 && cnt == sum / 2 + 1) || (sum % 2 == 0 && cnt == sum / 2))
{
prev = NULL;//此处就实现了链表的断开
while (b)//此时b就是后面链表的第一个结点的指针
{
b -> val = Node_val[tmp++] ;
b = b -> next;
}
tmp -= 1;//则Node_val里的数值就是从0到i的了
}
}
//(3)循环创建结点并插入已经被断开的链表中
ListNode * c = head;
for (int i = tmp; tmp > 0; tmp--)
{
ListNode tmp_Node = ListNode(Node_val[tmp]);
tmp_Node -> next = c -> next;//新创建的结点指向原链表结点的后一个结点
&tmp_Node = c -> next;//原链表结点指向新创建的结点
c = c -> next -> next;//因为插入了一个结点,所以c要往后移动两位才可以到变成即将要插入的结点的前驱
}
}