首页 > 试题广场 >

重排链表

[编程题]重排链表
  • 热度指数：129965 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
将给定的单链表：
重新排序为：
要求使用原地算法，不能只改变节点内部的值，需要对实际的节点进行交换。

数据范围：链表长度 ，链表中每个节点的值满足

要求：空间复杂度 并在链表上进行操作而不新建链表，时间复杂度
进阶：空间复杂度 ， 时间复杂度
示例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，点此查看相关信息
算法知识视频讲解
添加回答
C
fatzard头像 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)
C
在泡澡的喜羊羊很神奇头像 在泡澡的喜羊羊很神奇
// 递归一下
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)
C
子沐728592488头像 子沐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)
C
牛客123875127号头像 牛客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)
C
勇敢牛牛，不怕困难！头像 勇敢牛牛，不怕困难！ 
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)
C
牛客830308422号头像 牛客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条回答 44550浏览

热门推荐

通过挑战的用户

相关试题

重排链表

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号