首页 > 试题广场 >

重排链表

[编程题]重排链表

热度指数：132339 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

将给定的单链表 $\ L$ ： $L_0→L_1→…→L_{n-1}→L_ n$
重新排序为： $L_0→L_n →L_1→L_{n-1}→L_2→L_{n-2}→…$
要求使用原地算法，不能只改变节点内部的值，需要对实际的节点进行交换。

数据范围：链表长度 $0 \le n \le 20000$ ，链表中每个节点的值满足 $0 \le val \le 1000$

要求：空间复杂度 $O(n)$ 并在链表上进行操作而不新建链表，时间复杂度 $O(n)$

进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

示例1

输入

{1,2,3,4}

输出

{1,4,2,3}

说明

给定head链表1->2->3->4, 重新排列为 1->4->2->3,会取head链表里面的值打印输出 1

示例2

输入

{1,2,3,4,5}

输出

{1,5,2,4,3}

说明

给定head链表1->2->3->4->5, 重新排列为 1->5>2->4->3,会取head链表里面的值打印输出

示例3

输入

{}

输出

{}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

算法知识视频讲解

fatzard

void reorderList(struct ListNode* head ) {
    struct ListNode* p=head;
    struct ListNode* q=NULL;
    int len=0;
    while(p)
    {
        len++;
        p=p->next;
    }
    if(len<=1)return;
    p=head;
    int cnt=0;
    while(p)
    {
        cnt++;
        if(cnt==len/2)break;
        p=p->next;
    }
    q=p->next;
    p->next=NULL;
    p=head;
    struct ListNode* temp=NULL;
    while(q)
    {
        struct ListNode* w=q->next;
        q->next=temp;
        temp=q;
        q=w;
    }
    q=temp;
    struct ListNode* ans=NULL;
    cnt=0;
    while(p&&q)
    {
        cnt++;
        if(cnt%2==1)
        {
            if(cnt==1)ans=p,head=ans;
            else{
                ans->next=p;
                ans=p;
            }
            p=p->next;
        }
        else{
            ans->next=q;
            ans=q;
            q=q->next;
        }
    }
    if(q)ans->next=q;
    if(p)ans->next=p;
}

发表于 2023-10-15 15:22:14 回复(0)

在泡澡的喜羊羊很神奇

// 递归一下

void insertNode(struct ListNode *src, struct ListNode *dst)

{

src->next = dst->next;

dst->next = src;

}

void reorderList(struct ListNode* head ) {

if(!head || !head->next)

{

return;

}

struct ListNode *left = head;

struct ListNode *right = head->next;

struct ListNode *pre_end = head;

struct ListNode *end = pre_end->next;

while (pre_end->next->next) {

pre_end = pre_end->next;

end = pre_end->next;

}

if(left==pre_end || !end)

{

return;

}

insertNode(end, left);

pre_end->next = NULL;

left = right;

right = right->next;

reorderList(left);

}

发表于 2023-06-21 17:12:45 回复(0)

子沐728592488

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

/**
 * 
 * @param head ListNode类 
 * @return  void
 */

struct ListNode *FindLastNode(struct ListNode *head)
{
    if (head->next == NULL) {
        return head;
    }

    struct ListNode *temp = head->next;
    if (temp->next == NULL) {
        head->next = NULL;
        return temp;
    }

    return FindLastNode(head->next);
}

void reorderList(struct ListNode* head ) {
    // write code here
    struct ListNode *temp = head;
    struct ListNode *lastNode = NULL;

    if ((head == NULL) || (head->next == NULL)) {
        return;
    }

    while (temp != NULL) {
        lastNode = FindLastNode(temp);
        lastNode->next = temp->next;
        if (temp != lastNode) {
            temp->next = lastNode;
        }
        temp = lastNode->next;
    }
}

发表于 2022-11-16 00:29:49 回复(0)

牛客123875127号

typedef struct ListNode *ptr;
typedef ptr List;
typedef ptr Position;

    
static List list_findFromIndex(List x, unsigned int index);
static unsigned int list_findTotalCount(List x);
/**
 * 
 * @param head ListNode类 
 * @return  void
 */
void reorderList(struct ListNode* head ) {
    
    // write code here
    unsigned int listCount = list_findTotalCount(head);

    for(unsigned int i=1; (i + 2) < listCount; )
    {
        Position p, p1;
        int tempCell;
        
        p = (struct ListNode*)malloc(sizeof(struct ListNode));
        p = list_findFromIndex(head, i);
        tempCell = p->val; 

        p1 = head->next;
        for(unsigned int j=0; j < (listCount - i); j++)
        {
            p1 = p1->next;
        }

        p->val = p1->val;
        p1->val = tempCell;     

        i = i + 2;
        listCount = listCount - i - 1;
    }
}

List list_create(List x)
{
    x = (struct ListNode*)malloc(sizeof(struct ListNode));
    x->next = x;
    return x;
}

unsigned int list_findTotalCount(List x)
{
    unsigned int ret = 0;
    Position p = x->next;
    while( p != x)
    {
        p = p->next;
        ret ++;
    }
    return ret;
}

List list_findFromIndex(List x, unsigned int index)
{
    Position p = x;
    for(unsigned int i=0; i < index; i++)
    {
        p = p ->next;
    }
    return p;
}

void list_insert(Element element, List x)
{
    Position p = (struct ListNode*)malloc(sizeof(struct ListNode));
    p->val = element;
    p->next = x->next;
    x->next = p;
}


int main(int argc, char** argv)
{
    int test[] = {1, 2, 3, 4};
    List list;
    list = list_create(list);
    
    Position p = list->next;
    for(unsigned int i=0; i<4; i++)
    {
        list_insert(test[i], list);
    }
    reorderList(list);
    
    p = list->next;
    while(p->next != list) 
    {
        printf(" %d\r\n", p->val);
        p = p->next;
    }
    
    return 0;
}

自测是OK的

发表于 2022-01-28 14:52:03 回复(0)

勇敢牛牛，不怕困难！

const int N = 1e4;

typedef struct ListNode* NodePtr;

void reorderList(NodePtr head ) {
  // corrner case
  if (!head || !head->next) return;
  
  NodePtr stk[N];
  int top = -1;
  
  NodePtr slow = head, fast = head;
  while (fast && fast->next) {
    *(stk + ++top) = slow;
    slow = slow->next;
    fast = fast->next->next;
  }
  
  NodePtr p, q = fast ? slow->next : slow, nxt;
  while (top >= 0) {
    p = *(stk + top--);
    nxt = q->next;
    q->next = p->next;
    p->next = q;
    q = nxt;
  }
  
  slow->next = NULL;
}

发表于 2021-09-24 17:14:22 回复(0)

牛客830308422号

struct ListNode *reverseNode(struct ListNode *head)
{
    struct ListNode *pre = NULL;
    struct ListNode *cur = head;
    struct ListNode *next;
    while (cur) {
        next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

void reorderList(struct ListNode* head ) {
    // write code here
    if (head == NULL) {
        return;
    }
    struct ListNode *slow = head;
    struct ListNode *fast = head->next;
    struct ListNode *midNode;
    
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    midNode = slow->next;
    slow->next = NULL;
    midNode = reverseNode(midNode);

    slow = head;
    while (midNode) {
        struct ListNode *temp1 = slow->next;
        struct ListNode *temp2 = midNode->next;
        slow->next = midNode;
        midNode->next = temp1;
        slow = temp1;
        midNode = temp2;
    }
}

发表于 2021-09-20 00:15:19 回复(0)

提交观点

问题信息

链表

难度：

10条回答 805收藏 46759浏览

通过挑战的用户

查看代码

速度七十迈

2023-02-01 10:58:44
牛客31319...

2022-12-16 22:20:45
孙天发

2022-12-01 12:44:29
马里奥求被捞

2022-11-15 15:17:13
讨厌吃香菜的茶...

2022-10-10 22:19:02

重排链表

输入

输出

说明

输入

输出

说明

输入

输出

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

问题信息

热门推荐

通过挑战的用户

相关试题