Leetcode之重排链表

文章目录

• 前言
• 
  

  一、线性表

• 
  

  二、寻找链表中点 + 链表逆序 + 合并链表

• 总结

---

前言

题目如下：
重排链表(点我）

一、线性表

因为链表不能下标访问元素，所以我们不能随机访问链表中的元素，因此我们采用数组来存储链表中的每一个元素。

利用线性表可以随机访问元素的特点，可以轻松解决该题目。

具体代码如下：

void reorderList(struct ListNode* head) {
    if (head == NULL) {
        return;
    }
    struct ListNode* vec[40001];
    struct ListNode* node = head;
    int n = 0;
    while (node != NULL)//遍历将链表每个节点存储于数组vec中 
    {
        vec[n++] = node;
        node = node->next;
    }
    int i = 0, j = n - 1;
    while (i < j)//按照题目所述下标访问规律进行链接
     {
        vec[i]->next = vec[j];
        i++;
        if (i == j)//当i==j时退出循环
        {
            break;
        }
        vec[j]->next = vec[i];
        j--;
    }
    vec[i]->next = NULL;
}
代码来源：leetcode官方题解

空间复杂度0(n) 时间复杂度0(1)
这种方法还是非常好想的

二、寻找链表中点 + 链表逆序 + 合并链表

想进一步优化，必须要熟悉快慢指针找中间节点，链表逆序等，下面有这些题目的链接供大家参考：
链表的中间节点
反转链表
具体步骤：
1.找到原链表的中间节点
2. 将中间节点的后半部分反转
3. 按循序将二个链表交叉链接
过程如动图：
具体代码如下：

struct ListNode* getMid(struct ListNode* head)//获取中间节点
{
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}
struct ListNode* Swap(struct ListNode* head)//逆序
{
    struct ListNode* prev = NULL;
    struct ListNode* cur = head;
    struct ListNode* next = head->next;
    while (cur)
    {
        cur->next = prev;
        prev = cur;
        cur = next;
        if (next != NULL)
        {
            next = next->next;
        }
    }
    return prev;
}
void reorderList(struct ListNode* head) {
    if (head == NULL)
    {
        return;
    }
    if(head->next==NULL)
    {
        return;
    }
    struct ListNode* mid = getMid(head);
    struct ListNode* cur = head;
    struct ListNode* prev = head;
    while (cur != mid)
    {
        prev = cur;
        cur = cur->next;
    }
    prev->next = NULL;
    struct ListNode* p2 = Swap(mid);
    struct ListNode* p1 = head;
    struct ListNode* next1 = p1;
    struct ListNode* next2 = p2;
    cur = head;
    int n = 1;
    while (next1 != NULL)
    {
        if (n % 2 != 0)
        {
            next1 = cur->next;
            cur->next = next2;
            cur = cur->next;
        }
        else
        {
            next2 = cur->next;
            cur->next = next1;
            cur = cur->next;
        }
        n++;
    }
}

总结

以上就是重组链表的全部内容希望对大家有帮助!