首页 > 代码库 > Reorder List

Reorder List

2024-08-02 10:17:51   217人阅读

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes‘ values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

链表虽然好做，但是为什么每次都有那么点错误呢？？？？

C++代码实现：

#include<iostream>#include<new>using namespace std;//Definition for singly-linked list.struct ListNode{    int val;    ListNode *next;    ListNode(int x) : val(x), next(NULL) {}};class Solution{public:    void reorderList(ListNode *head)    {        //开始的代码因为没有加入head->next==NULL而不被接受        if(head==NULL||head->next==NULL)            return;        int len=0;        ListNode *l1=head;        ListNode *l2=NULL;        while(l1)        {            len++;            l1=l1->next;        }        len=(len+1)/2;        l1=head;        while(--len)        {            l1=l1->next;        }        if(l1->next==NULL)            return;        l2=l1->next;        l1->next=NULL;        ListNode *p=l2->next;        l2->next=NULL;        ListNode *q=NULL;        while(p)        {            q=p->next;            p->next=NULL;            p->next=l2;            l2=p;            p=q;        }        l1=head;        p=l2;        while(l1&&l2)        {            l2=l2->next;            p->next=NULL;            p->next=l1->next;            l1->next=p;            p=l2;            l1=l1->next->next;        }    }    void createList(ListNode *&head)    {        ListNode *p=NULL;        int i=0;        int arr[11]= {10,9,8,7,6,5,4,3,2,1};        for(i=0; i<10; i++)        {            if(head==NULL)            {                head=new ListNode(arr[i]);                if(head==NULL)                    return;            }            else            {                p=new ListNode(arr[i]);                p->next=head;                head=p;            }        }    }};int main(){    Solution s;    ListNode *L=NULL;    s.createList(L);    ListNode *head=L;    while(head)    {        cout<<head->val<<" ";        head=head->next;    }    cout<<endl;    s.reorderList(L);    while(L)    {        cout<<L->val<<" ";        L=L->next;    }}

运行结果：

开始提交时报错，

Input:    {1}Output:    1Expected:    {1}

没看懂，在刚开始的判断条件中加了

head->next==NULL 就通过了。

Reorder List


联系
我们