力扣练习——重排链表

1.问题描述

给定一个单链表 L：L0→L1→…→Ln-1→Ln ，

将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

 

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

 

示例 1:

给定链表 1->2->3->4, 重新排列为 1->4->2->3.

示例 2:

给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

 

可使用以下代码，完成其中的reorderList函数，其中形参head指向无头结点单链表。

#include<iostream>

using namespace std;

 

struct ListNode

{

    int val;

    ListNode *next;

    ListNode() : val(0), next(NULL) {}

    ListNode(int x) : val(x), next(NULL) {}

    ListNode(int x, ListNode *next) : val(x), next(next) {}

};

 

class Solution

{

public:

    void reorderList(ListNode* head)

    {

             //填充本函数完成功能

    }

};

ListNode *createByTail()

{

    ListNode *head;

    ListNode *p1,*p2;

    int n=0,num;

    int len;

    cin>>len;

    head=NULL;

    while(n<len && cin>>num)

    {

        p1=new ListNode(num);

        n=n+1;

        if(n==1)

            head=p1;

        else

            p2->next=p1;

        p2=p1;

    }

    return head;

}

 

void  displayLink(ListNode *head)

{

    ListNode *p;

    p=head;

    cout<<“head–>”;

    while(p!= NULL)

    {

        cout<<p->val<<“–>”;

        p=p->next;

    }

    cout<<“tail/n”;

}

int main()

{

    ListNode* head = createByTail();

    Solution().reorderList(head);

    displayLink(head);

    return 0;

}

 

2.输入说明

首先输入链表长度len，然后输入len个整数，以空格分隔。

3.输出说明

输出格式见范例

4.范例

输入

5
1 2 3 4 5

输出

head–>1–>5–>2–>4–>3–>tail

5.代码

#include<iostream>

using namespace std;



struct ListNode

{

    int val;

    ListNode *next;

    ListNode() : val(0), next(NULL) {}

    ListNode(int x) : val(x), next(NULL) {}

    ListNode(int x, ListNode *next) : val(x), next(next) {}

};



class Solution

{

public:

    //2.1使用头插法进行逆转
    ListNode *reverse(ListNode *head)
    {
        if (head == NULL || head->next == NULL) return head;
        ListNode *pre = NULL,*cur=head ;
        while (cur != NULL)
        {
            ListNode *tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
    //3.将两个不带头结点的单链表进行合并操作
      ListNode *merge(ListNode *left, ListNode *right) {

        struct ListNode *dummy=(ListNode*)malloc(sizeof(ListNode));//dummy指向链表头结点
        struct ListNode *t = dummy;//t指向新链表尾部
        while (left != NULL && right != NULL) {
            t->next = left;
            t = t->next;
            left = left->next;

            t->next = right;
            t = t->next;
            right = right->next;
        }
        if (left != NULL) {
            t->next = left;
            t = t->next;
            left = left->next;

        }

        if (right != NULL) {
            t->next = right;
            t = t->next;
            right = right->next;

        }

        return dummy->next;
    }
    

    void reorderList(ListNode* head)

    {
        if (head == NULL) return;
        /*
        //1.找到中间结点【法一：计算链表长度，遍历到中间结点，但是要注意向下取整】
        struct ListNode* p = head;
        int len = 0;//计算链表长度
        while (p != NULL)
        {
            len++;
            p = p->next;
        }
            p = head; //从头开始
        for (int i = 0; i < (len + 1) / 2 - 1; i++)
            p = p->next; 

        struct ListNode* a = p; //a指向中间结点
        struct ListNode* b = p->next;//b指向中间结点的后继
        */
        //寻找中间结点【法二：使用快慢指针的方法，更加简单；最终指针指向的就是中间结点】
        struct ListNode *fast = head;
        struct ListNode *slow = head;

        while (fast != NULL && fast->next != NULL)
        {
                fast = fast->next->next;//快指针每次跳两格
                slow = slow->next;//慢指针每次跳一格 
        }
         
        struct ListNode* a = slow;
        struct ListNode* b = slow->next;

        /*
        //2.将后半部分链表进行反转【单链表的逆转写法】
        
        while (b)  //b所指开始为后半部分链表，直接在原链表进行操作
        {
            ListNode *mm = b->next; //保留b的next节点
            b->next = a;
            //cout << "b=" <<b->val<<" "<<"a="<<a->val<<endl;
            a = b, b = mm;
            
        }
        
        //3.将反转后的链表插入到原链表的前半部分

        slow->next = NULL;
        ListNode *s;
        while (head != NULL && head != a)
        {
            s = a->next;//s指向后半部分链表的第一个结点，即s==slow->next==b
            a->next = head->next;//接下来两步将a所指结点插入到head之后
            head->next = a;
            head = head->next->next;//将head指向新插入结点的后面，即head->next->next
            a = s;
        }
        */

        
        ListNode *left = head; //第一个链表
        ListNode *right = reverse(b);//第二个链表
        slow->next = NULL;//链表尾部结点记得要置空
        head=merge(left, right);//这里head为最终的链表的头结点


    }
    

};

ListNode *createByTail()

{

    ListNode *head;

    ListNode *p1, *p2=NULL;

    int n = 0, num;

    int len;

    cin >> len;

    head = NULL;

    while (n<len && cin >> num)

    {

        p1 = new ListNode(num);

        n = n + 1;

        if (n == 1)

            head = p1;

        else

            p2->next = p1;

        p2 = p1;

    }

    return head;

}



void  displayLink(ListNode *head)

{

    ListNode *p;

    p = head;

    cout << "head-->";

    while (p != NULL)

    {

        cout << p->val << "-->";

        p = p->next;

    }

    cout << "tail/n";

}

int main()

{

    ListNode* head = createByTail();

    Solution().reorderList(head);

    displayLink(head);

    return 0;

}