【每日刷题】Day16

 //0ms  100%思路:创建新链表,malloc新节点按照题目所给顺序存储原链表节点,新链表逐个连接新节点

typedef struct ListNode LN;


 

 int ListNodeQua(LN* phead)//计算原链表节点数

 {

    LN* pmove = phead;

    int count = 0;

    while(pmove)

    {

        count++;

        pmove = pmove->next;

    }

    return count;

 }

struct ListNode* swapPairs(struct ListNode* head)

{

    if(head==NULL)

    {

        return NULL;

    }

    if(head->next==NULL)

    {

        return head;

    }


 

    int n = ListNodeQua(head);

    LN* sentry = (LN*)malloc(sizeof(LN));//新链表哨兵位

    LN* pmove = head;//原链表奇数位节点

    LN* pmove1 = sentry;//用于遍历新链表连接新节点

    int i = 0;

    while(i<n/2)//交换次数即为循环次数

    {

        LN* pmove2 = pmove->next;//原链表偶数位节点

        LN* pget1 = (LN*)malloc(sizeof(LN));//新节点1

        pget1 = pmove2;//存储原链表偶数位节点

        pmove1->next = pget1;//连接新节点

        pmove1 = pmove1->next;//往后遍历以连接下一个节点

        LN* pget2 = (LN*)malloc(sizeof(LN));//新节点2

        pget2 = pmove;//存储原链表奇数位节点

        pmove->next = pmove2->next;//这里需要注意,由于原链表奇数位节点的next指向后一个偶数位节点,而下面我们在让新链表连接新节点时,会导致相邻两个节点成环,因此这里需要在新链表连接新节点前让奇数位节点的next指向下一个奇数位节点

        pmove1->next = pget2;//连接新节点

        pmove1 = pmove1->next;//往后遍历以连接下一个节点

        pmove = pmove->next;//由于上面我们奇数位节点next指向了下一个奇数位节点,因此这里直接走向next即可进行下一个交换

        i++;

    }

    LN* phead = head;

    if(n%2==1)//如果链表个数为奇数个,则在最后一次交换后会遗漏下最后一个节点,这里只需要直接将最后一个节点连接上即可

    {

        while(phead->next)

        {

            phead = phead->next;

        }

        pmove1->next = phead;

    }

    return sentry->next;

}

上一篇:apk反编译