Insert Num in Circle List

发表于 2017-03-26 | 分类于算法

Insert Num To Circle List（向环链表中插入节点）

题目描述：

给定一个链表的头节点，和一个目标值。已知该链表从头部开始不降序，且最后一个节点指向了头节点；要求将该值插入链表后并保持链表仍旧有序。

例子：

1->3->4->1将节点5插入链表后得到1->3->4->5->1。

解题思路：

首先判断链表头节点是否为空，如果是空的情况，我们就将插入节点自己形成环链表返回即可。不为空的情况下，我们将pre指向head，将cur指向head->next。然后判断插入值和pre以及cur节点之间的关系。如果在二者之间我们就将数据插入即可；如果不是则继续向下遍历；当遍历一圈之后，如果都没找到合适的节点插入，说明这个插入值不是比所有的节点小，就是比所有的节点大。插入到头节点的上一个节点即可。注意这两种情况虽然进行操作一样，但是返回的头结点不一样。

代码如下：

class insertNum1{
public:
    ListNode* insertNum(ListNode* head, int num){
        ListNode* node = new ListNode(num);
        if (head == NULL){
            node->next = node;
            return node;
        }  // 头节点为空情况
        ListNode* pre = head;
        ListNode* cur = head->next;//记录前后两个节点用于遍历链表
        while(cur != head){
            if (pre->val <= num && cur->val >= num){
                break;  //该情况跳出循环然后插入节点
            }else{
                cur = cur->next;
                pre = cur; //不然继续遍历即可
            }
        }
        pre->next = node;
        node->next = cur;
        return head->val < num ? head : node;//不同情况返回不同头结点
    }
};

Delete Node In List

发表于 2017-03-25 | 分类于算法

Delete Node In List(删除链表中指定值的节点)

题目描述1：

给定一个链表的头结点，和一个目标值。要求将链表中与目标值相同的节点全部删除。

例子：

链表为1->1->2->3->1->1->2->NULL；目标值为1，则删除后的链表为：2->3->2->NULL。

解题思路1：

第一种解题思路是将链表中的节点依次的压入栈，在压栈的过程中判断当前节点是否和目标值相同，相同的节点不入栈。然后从栈顶不断取出元素将其重新连接起来将头结点返回即可。

代码如下：

class removeSpecificValue1{
public:
    ListNode* removeSpecificValue(ListNode* head, int value){
        std::stack<ListNode*> stk;//定义栈用于保存元素
        while(head != NULL){
            if (head->val != value){
                stk.push(head);
                head = head->next;
            }
            else
                head = head->next;
        }                     //将元素不断入栈
        while(!stk.empty()){
            stk.top()->next = head;
            head = stk.top();
            stk.pop();
        }                   //重新连接元素
        return head;
    }
};

解题思路2：

在考虑不用额外空间的情况下，我们的做法是遍历链表的过程中直接将该元素删除即可。需要注意的地方在于开头需要先找到不等于目标值的节点，还有记录删除节点的上一个节点。

代码如下：

class removeSpecificValue1{
public:
    ListNode* removeSpecificValue(ListNode* head, int value){
        if (head == NULL)
            return head;
        while(head != NULL){
            if (head->val != value){
                break;
            }
            else{
                head = head->next;
            }
        }  // 找到第一个节点作为开头
        ListNode* pre = head; // 记录删除节点的前一个节点
        ListNode* cur = head->next;
        while(cur != NULL){
            if (cur->val == value){
                pre->next = cur->next;
                cur = pre->next;
            }
            else{
                pre = pre->next;
                cur = cur->next;
            }
        }
        return head;
    }
};

题目描述2：

给定链表中的一个节点的指针，要求删除这个节点。

例子：

具体描述可以看LeetCode237

解题思路：

这一题比较巧妙的地方是我们不知道链表的头结点，而且我们无法逆序找到头节点。唯一的方法是，我们用下一个节点的值代替当前节点，然后删除下一个节点。

代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        if (!node->next){
            node = NULL;
            //尾部节点的情况
        }else {
            node->val = node->next->val;
            node->next = node->next->next;
            //替换节点值和删除下一个节点
        }
        
    }
};

Remove Duplicate

发表于 2017-03-24 | 分类于算法

Remove Duplicate(删除链表中的重复节点)

题目描述1：

给定一个无序链表的头节点，删除其中出现重复的节点。

例子：

1->2->3->3->4->4-2->1->1->NULL。删除其中的重复节点后得到1->2->3->4->NULL。

解题思路：

首先我们第一个想法是记录下当前遍历过程中已经出现过的节点，这样在不断的遍历过程中只要是已经出现过的节点就直接删除。所以利用哈希表的思路。用一个哈希表记录遍历过程中得到的节点，然后每次遍历判断是否在表中，不在的情况加入表；在的情况下就直接删除当前节点。

代码如下：

class removeRepeatValue1{
public:
    ListNode* removeRepeatValue(ListNode* head){
        if (head == NULL || head->next == NULL)
            return head;
        std::set<int> num; // 构建哈希表
        ListNode* pre = head;
        ListNode* cur = head->next;
        num.insert(pre->val); 
        //第一个节点肯定不是重复的，从第二个节点开始遍历
        while(cur != NULL){
            if (num.find(cur->val) == num.end()){
                num.insert(cur->val);
                cur = cur->next;
                pre = pre->next;//如果不在哈希表中
            }
            else{
                pre->next = cur->next;
                cur = pre->next; // 如果在则删除当前节点
            }
        }
        return head;
    }                   //同样删除链表中的节点需要注意保持前一个节点
};

解题思路2：

当然哈希表直观简单，但是利用了较多的空间。所以利用下面这种方法可以减少空间复杂度，同样时间复杂度会较高。

主要的想法是，首先遍历第一个节点，然后找到链表中所有和该节点相同的节点，删除掉，然后遍历下一个节点。时间复杂度为O(N^2)，空间复杂度为O(1)。

代码如下：

class removeRepeatValue2{
public:
    ListNode* removeRepeatValue(ListNode* head) {
        if (head == NULL || head->next == NULL)
            return head;
        ListNode *step = head;
        while (step != NULL) {
            int flag = step->val; //记录当前节点的值
            ListNode *cur = step->next;
            ListNode *pre = step;
            while (cur != NULL) {
                if (cur->val == flag) {
                    pre->next = cur->next;
                    cur = pre->next;
                } else {
                    cur = cur->next;
                    pre = pre->next;
                }  // 如果有和当前节点值相同的，删除掉
            }
            step = step->next; // 遍历下一个节点
        }
        return head;
    }
};

题目描述2：

给定一个有序链表的头节点，删除其中出现只要重复的所有节点。

例子：

1->2->3->3->4->4->NULL。删除其中的重复节点后得到1->2->NULL。

解题思路：

主要的难点在于头结点情况的处理，这边用了虚拟头结点来处理删掉头节点的情况。然后不断用flag遍历代表当前要判断是否重复的节点，分成重复和不重复两种情况处理。注意在找下一个节点和当前节点是否相同的时候需要加上head->next。

代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        //定义虚拟头节点方便删除头节点
        ListNode* pre = dummy;
        while(head){
            ListNode* flag = head;
            //flag为当前判断是否重复的节点
            while(head->next && head->next->val == head->val){
                head = head->next;
                //一直遍历到和flag节点的值不同为止
            }
            if (head == flag){
                pre = flag;
                head = flag->next;
                //下一个节点和上一个节点不重复的情况
            }else{
                pre->next = head->next;
                head = head->next;
                //重复的情况
            }
        }
        return dummy->next;
    }
};

Partition List

发表于 2017-03-23 | 分类于算法

Partition List(将链表按照某个值分区)

题目描述：

给定一个链表的头结点和一个给定值k。将链表按照左侧的节点都小于k，中间的值等于k，右侧的值大于k的排列方式重新连接链表。对于链表各个分区的内部节点并没有要求有序，但是要求和原链表中的节点顺序一致。

例子：

9->0->4->5->1->NULL。给定的分区值为3的情况下，我们需要返回的链表为：0->1->9->5->4->NULL

解题思路：

主要的思路是我们定义3个分区链表，分别保存小于分区值、等于分区值和大于分区值3种。然后遍历链表不断的将链表的节点加入对应的分区链表中，最后再将三个分区链表连接即可。注意的地方有在连接三个分区的时候，需要考虑各个分区中可能是空的情况。

代码如下：

class listPartition1{
public:
    ListNode* listPartition(ListNode* head, int pivot){
        ListNode* sh = NULL;
        ListNode* se = NULL; // 小于分区值的头节点和尾节点
        ListNode* eh = NULL;
        ListNode* ee = NULL; // 等于分区值的头节点和尾节点
        ListNode* bh = NULL;
        ListNode* be = NULL; // 大于分区值的头节点和尾节点
        ListNode* next = NULL;
        while(head != NULL){
            next = head->next;
            head->next = NULL; // next保存下一个节点后断开当前节点和后续链表的连接
            if (head->val < pivot){
                if (sh == NULL){
                    sh = head;
                    se = head;
                }
                else{
                    se->next = head;
                    se = se->next;
                }             // 将符合条件的节点放入对应分区
            } else if (head->val == pivot){
                if (eh == NULL){
                    eh = head;
                    ee = head;
                }
                else{
                    ee->next = head;
                    ee = ee->next;
                }          // 将符合条件的节点放入对应分区
            }else{
                if (bh == NULL){
                    bh = head;
                    be = head;
                }
                else{
                    be->next = head;
                    be = be->next;
                }        // 将符合条件的节点放入对应分区
            }
            head = next; // 然后head继续遍历
        }
        if (sh != NULL){
            if (eh != NULL) {
                se->next = eh;
                ee->next = bh;
            }
            else
                se->next = bh;
            return sh;
        }
        else{
            if (ee != NULL) {
                ee->next = bh;
                return ee;
            }
            else
                return bh;  //需要注意不同的分区可能为空的情况
        }
    }
};

Palindrome List

发表于 2017-03-22 | 分类于算法

Palindrome List(判断链表是否是回文链表)

题目描述：

给定一个链表的头结点，判断链表是否是回文结构。

例子：

1->2->3->2->1->NULL即为回文链表

解题思路1：

回文的结构的特点是正序和逆序的访问结果是一致的。所以第一种想法是利用栈结构来逆序链表。首先申请一个栈空间，然后遍历链表，将链表中的数据不断的压栈。然后再次遍历链表和栈，如果出现栈中的数据和链表中的数据不一致的情况即为非回文结构。

代码如下：

class isPalindrome1{
public:
    bool isPalindrome(ListNode* head){
        stack<int> stk; // 申请栈空间
        ListNode* temp = head;
        while(temp != NULL){
            stk.push(temp->val);
            temp = temp->next;
        }             //数据压栈
        while(head != NULL){
            if (stk.top() != head->val) {
                return false;
            }          
            else{
                stk.pop();
                head = head->next;
            }
        }        //判断元素是否相同
        return true;
    }
};

解题思路2:

在原先的基础上我们可以通过找到链表的中间节点，然后用先前的栈的一半空间即可实现。主要想法是我们可以找到例子中的中间节点3；然后我们可以将后半部分2->1->NULL压栈；然后从链表头部和栈顶开始遍历数据判断是否相等即可。

class isPalindrome2{
public:
    bool isPalindrome(ListNode* head){
        ListNode* cur = head;
        ListNode* right = head->next;
        if (head == nullptr || right == NULL)
            return false;
        while(cur->next != nullptr && cur->next->next != NULL){
            right = right->next;
            cur = cur->next->next;
        }//找到中间节点
        stack<int> stk;
        while(right != NULL){
            stk.push(right->val);
            right = right->next;
        } //压栈
        while(!stk.empty()){
            if (stk.top() != head->val)
                return false;
            else{
                stk.pop();
                head = head->next;
            }
        }//判断是否相等
        return true;
    }
};

解题思路3:

判断回文的过程中，我们遇到的另外一个问题是对于链表我们无法逆序查找，如果可以的话我们就可以直接从链表的头部和尾部同时查找然后判断是否是回文即可。所以基于这个思路，我们可以将链表的后半段改变指针的指向后，然后从左右侧同时开始遍历判断是否相等即可。

class Solution3 {
public:
    bool isPalindrome3(ListNode* head) {
        if (head->next == NULL || head->next->next == NULL)
            return true;
        ListNode* n1 = head;
        ListNode* n2 = head;
        while(n2->next != NULL && n2->next->next != NULL){
            n1 = n1->next;
            n2 = n2->next->next;
        }             //快慢指针找到链表的中部节点
        n2 = n1->next;
        n1->next = NULL;
        ListNode* n3 = NULL;
        while(n2 != NULL){
            n3 = n2->next;
            n2->next = n1;
            n1 = n2;
            n2 = n3;
        }           //逆序后半部分链表
        n3 = n1;
        n2 = head;
        while(n1 != NULL && n2 != NULL){
            if(n1->val != n2->val){
                return false;
            }
            else{
                n1 = n1->next;
                n2 = n2->next;
            }
        } // 从左右侧同时遍历链表判断值是否相等
        return true;
    }
};

Reverse Every K Node In List

发表于 2017-03-21 | 分类于算法

Reverse Every K Node In List(将每k个节点逆序)

题目描述：

给定一个链表的头结点head，和一个整数K。将链表中从头到尾链表中的每k个节点逆序，如果最后一段不足k个节点的不进行逆序。

例子：

1->2->3->4->5->6->7->8->NULL.给定的k值为3.则返回的链表排列为:3->2->1->6->5->4->7->8->NULL。

解题思路：

首先涉及到了逆序，第一个想法是利用栈的结构，能够帮助我们将链表中的数据逆序。所以新建一个栈结构和一个计数值，将链表中的值不断压栈，利用计数值来判断是否达到了K个节点。如果达到的话，则从栈中不断出栈数据，然后修改链表中的数据即可。

代码如下：

#include "ListNode.h"
#include <stack>
using namespace std;
class reverseKNodes1{
public:
    ListNode* reverseKNodes(ListNode*head, int K){
        if (K < 2)
            return head; // 逆序K小于2的情况直接返回
        stack<int> stk;
        int count = 0;
        ListNode* cur = head;//用来记录当前的遍历节点
        ListNode* tmp = head;//用来保存每k个节点的头节点
        while(cur != NULL){
            if (count != K){
                stk.push(cur->val);
                count = count + 1;
                cur = cur->next;
            }// 将数据进栈，直到栈中k个数
            else{
                while(!stk.empty()){
                    tmp->val = stk.top();
                    stk.pop();
                    tmp = tmp->next;
                }//根据出栈的数修改链表中的数据
                tmp = cur;// 重新修改当前每k个小链表的头节点
                count = 0;
            }
        }
        return head;
    }
};

解题思路2：

当然我们也可以不用栈结构直接进行链表的调整。主要的思路是用start记录每k个节点的头，end用来记录k个节点的尾。然后直接将k个节点进行逆序。主要需要注意的地方有：第一组k个节点的尾部成为返回的头节点，需要记录；另外后面的每组k个节点，我们都需要将逆序后的k个节点的头部与上一组的k个节点的尾部重新连接。

代码如下：

class reverseKNodes2{
public:
    ListNode* reverseKNodes(ListNode* head, int K){
        if (K < 2)
            return head;
        ListNode* cur = head; //遍历节点
        ListNode* start = NULL;
        ListNode* pre = NULL; // 上一组k个节点的尾部
        ListNode* next = NULL; //下一组k个节点的头部
        int count = 1;
        while(cur != NULL){
            next = cur->next;
            if (count == K){
                start = pre == NULL ? head : pre->next;
                head = pre == NULL ? cur : head;// 记录返回的头结点
                resign(pre, start, cur, next);// 逆序函数
                pre = start;// 修改pre节点
                count = 0;
            }
            count++;
            cur = next;
        }
        return head;
    }
    void resign(ListNode* left, ListNode* start, ListNode* end, ListNode* right){
        ListNode* pre = start;
        ListNode* cur = start->next;
        ListNode* next = NULL;
        while (cur != right){
            next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        if (left != NULL){
            left->next = end;
        }
        start->next = cur;
    }
};

Print Common Part In List

发表于 2017-03-20 | 分类于算法

PrintLists(打印链表的公共部分)

题目描述：

给定两个有序链表的头结点，要求打印出两个链表中的公共节点部分。题目思路很简单，分别从两个链表头部开始遍历，判断其值的大小决定各自遍历指针是否移动，相等的情况就打印就可以。

代码如下：

class printCommonPart1 {
public:
    void printCommonPart(ListNode* head1, ListNode* head2) {
        while( head1 != NULL && head2 != NULL){
            if (head1->val == head2->val){
                cout << head1->val << endl;
                head1 = head1->next;
                head2 = head2->next;
            }      // 相同的情况打印并同时移动遍历指针
            else if (head1->val > head2->val){
                head2 = head2->next;
            }    
            else if (head1->val < head2->val) {
                head1 = head1->next;
                // 较小的指向值指针移动
            }
        }
    }
};

Delete the Kth Node In List

发表于 2017-03-19 | 分类于算法

Delete List Node(删除链表中的第倒数第k个节点)

题目描述：

给定一个链表的第头节点，要求删除链表中的倒数第k个节点。

例子：

1->2->3->4->5->NULL.比如删除倒数第二个节点4，要求返回链表头节点包含1->2->3->5->NULL.

解题思路：

因为单项链表无法向前遍历的特点，所以我们可以用一个指示节点来帮助我们找到链表中的倒数第k个节点。做法是：先定义一个指向指针，从链表头结点开始遍历先走k步；而后再定义个遍历指针从链表头部开始遍历，当指示节点遍历到链表尾部的时候，这个时候后遍历的指针刚好达到链表中的第k个节点。需要注意的是，我们删除第k个节点，需要知道第k-1个节点的指针，所以要定义一个pre指针用来保存待删除节点的前一个节点。

代码如下：

class removeLastKthNode1{
public:
    ListNode* removeLastKthNode(ListNode* head, int lastKth){
        if (head == NULL || lastKth < 1)
            return head ;
        ListNode* cur = head;
        while(cur != NULL){
            cur = cur->next;
            lastKth--;
        }     // 先走k步的指示指针
        if (lastKth == 0) {
            return head->next;
            // k的大小大于链表长度的情况
        }
        if (lastKth < 0){
            cur = head;
            while (lastKth != -1){
                cur = cur->next;
                lastKth++;
            }
            cur->next = cur->next->next;
        }    // 删除找到的节点
        return head;
    }
};

延伸题目1:

链表中的中间节点。与上面的思路一样，利用快慢指针的方法就可以找到链表的中间节点。首先定义快指针fast和慢指针slow，快指针每次走两步，慢指针一次走一步。这样当快指针到达链表末尾的时候，慢指针刚好到达链表的中间节点部分。同样记得记录待删除节点的前一个节点。

代码如下：

class removeMidNode1{
public:
    ListNode* removeMidNode(ListNode* head){
        if (head == NULL || head->next == NULL)
            return head;
        if (head->next->next == NULL)
            return head->next;
        ListNode* slow = head;
        ListNode* fast = head->next->next;//定义快慢指针
        while(fast->next != NULL && fast->next->next != NULL){
            slow = slow->next;
            fast = fast->next->next;
        }                                 //找到链表的中间节点
        slow->next = slow->next->next;
        return head;
    }
};

延伸题目2:

给定一个链表的头节点和整数a和整数b。要求删除链表中a/b地方的节点。这一题的主要麻烦之处是找到要删除的节点在链表中的位置，所以a/b在链表中的位置该怎么找事关键。这边主要用到的是(a*n)/b公式，得到的数值即为要删除节点在链表中的位置。

代码如下:

class removeByRation1{
public:
    ListNode* removeByRation(ListNode* head, int a, int b){
        if (a < 0 || a > b)
            return head;
        int n = 0;
        ListNode* cur = head;
        while(cur != NULL){
            cur = cur->next;
            n++;
        }            // 计算链表的长度
        int kth = int(ceil(double(a * n) / double(b)));
                   // 找到链表的位置
        if (kth == 1)
            return head->next;  //如果是头节点的情况
        if (kth > 1) {
            cur = head;
            while (--kth != 1) {
                cur = cur->next;
            }
            cur->next = cur->next->next;
        }
        return head;
    }
};

Copy List With Random Indicator

发表于 2017-03-18 | 分类于算法

CopyList(拷贝带有随机节点的链表)

题目描述：

给定一个链表节点结构的新定义，其中链表节点在包含下一个节点指针的情况下，还包含指向random的指针。其中指向random的指针可以指向任意在链表中的节点，或者为空。其定义如下。题目要求给定一个链表的头结点，其节点结构如定义中所诉。要求复制该链表，并返回新建链表的头结点。

#include <iostream>
struct randomListNode{
    int val;
    randomListNode* next;
    randomListNode* rand;
    randomListNode(int x): val(x), next(NULL), rand(NULL) {};
};

例子：

假设链表结构为如下:1->2->3->NULL。其中1节点的random指针指向3；2的random指针指向NULL；3的random指针指向2。

解题思路1：

解题的第一种思路是构造hash表。其中key是旧表的节点，value是与旧表节点值相同的新建节点。

key value

1 1’

2 2’

3 3’

然后我们不断遍历key的next指针，将value的next的指针连接；然后遍历key的random指针将value的关系连接。举例遍历到1的时候，我们检查1节点的random指针是3，则将1’的random指针指向3’即可。

key	value
1	1’
2	2’
3	3’

解法1代码如下：

#include "randonListNode.h"
#include <map>
class copyListWithRand1{
public:
    randomListNode* copyListWithRand(randomListNode* head){
        std :: map<randomListNode*, randomListNode*> HashTable;
        randomListNode* cur = head;
        while(cur != NULL){
            randomListNode* tmp = new randomListNode(cur->val);
            HashTable.insert({cur, tmp});
            cur = cur->next;
        }                  //构造hash表
        cur = head;
        while(cur != NULL){
            HashTable[cur]->next = HashTable[cur->next];
                          // 重新连接next指针
            HashTable[cur]->rand = HashTable[cur->rand];
                          //重新连接random指针
            cur = cur->next;
        }
      return HashTable[head];
    }
};

解法2的思路：

解法1的思路是利用hash表找到旧节点和新节点之间的关系，通过一个新的方式我们可以不用hash表的方式做到。主要的方法是我们通过1->2->3->NULL.来构建一个新的链表1->1’->2->2’->3->3’->NULL。这样我们就知道了新节点肯定在旧节点的next指针下。然后通过遍历旧节点的random指针改变新节点的random指针；再将这个链表拆分返回头结点即可。

解法2代码如下：

class copyListWithRand2{
public:
    randomListNode* copyListWithRand(randomListNode* head){
        if (head == NULL) {
            return head;
        }
        randomListNode* cur = head;
        while(cur != NULL){
            randomListNode* tmp = new randomListNode(cur->val);
            tmp->next = cur->next;
            cur->next = tmp;
            cur = cur->next->next;
        }                  //重新构造带有新旧节点的链表
        cur = head;
        while(cur != NULL){
            cur->next->rand = cur->rand == NULL ? NULL : cur->rand->next;
            cur = cur->next->next;
        }                // 改变random指针。注意判断指针是否为空
        cur = head->next;
        randomListNode* result = cur;
        while(head != NULL){
            head->next = head->next->next;
            cur->next = cur->next == NULL ? NULL : cur->next->next;                  // 拆分新旧链表的节点，也是注意判断空节点
            head = head->next;
            cur = cur->next;
        }
        return result;
    }
};

Relocate List

发表于 2017-03-17 | 分类于算法

根据左右半区重新排列链表

题目描述：

给定一个链表的头结点，其长度为N。如果长度为偶数的情况下，认为前N/2为左半区，后N/2为右半区；如果N为奇数，则认为前N/2为左半区，后N/2+1为右半区。根据如下例子中规则重新排列链表。

例子：

假设原链表为1->2->3->4->5->NULL,调整后为1->3->2->4->5->NULL。

解题思路：

主要的解题思路在于找到链表的中间节点。中间节点即为右区开始节点的上一个节点。而后一个指针指向左半区开始节点，一个指针指向右半区开始节点；不断调整链表的指向即可。需要注意的地方是根据规则找到中间节点，和找到中间节点后需要将左右半区断开。

代码如下：

#include "ListNode.h"
class relocateList1{
public:
    ListNode* relocateList(ListNode* head){
        if (head == NULL || head->next == NULL)
            return head;
        ListNode* right = head->next;
        ListNode* left = head;
        while(right->next != NULL && right->next->next != NULL){
            left = left->next;
            right = right->next->next;
        }                  // 找到链表的中间节点。
        right = left->next;
        left->next = NULL; // 断开左右半区的连接
        left = head;
        ListNode* next1 = NULL;
        ListNode* next2 = NULL;
        while(left->next != NULL){
            next1 = left->next;  //记录左当前节点的下一个节点
            next2 = right->next; //记录右当前节点的下一个节点
            left->next = right;
            right->next = next1; // 重新调整链表的指向
            left = next1;
            right = next2;       //进行下一次的遍历
        }
        left->next = right;
        return head;
    }
};