143重排链表

143.重排列表

下面是题目

下面是题目给出的模板

/**
 * 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) {
       
    }
};

• 我首先想到了反转链表，然后拉链法互相指，在原理上是可行的，但是需要两根链表，题目只给我们一根，如果要再建立一根一模一样的再反转，显然太麻烦。所以我看了解题思路。

第一种，就是多次遍历

class Solution {
public:
    void reorderList(ListNode* head) {
        ListNode *first = head;
        ListNode *last = head;
        //首先让头尾节点都指向头，然后呢，每次都将尾节点移到末尾，让头节点指向尾节点。然后更新头节点
        while(first&&first->next&&first->next->next)
        {
            //在这里新建一个临时节点，它的作用就是指向最后一个节点的前一个节点，然后“脱钩”
            ListNode *temp ;
            while(last->next)
            {
                temp= last ;
                last =last->next;
            }
            //这时候，尾节点是独立出来的，倒数第二个节点成为了尾节点
            //这时候尾节点已经不是原来的尾节点了！实现了尾节点的更新
            temp->next = NULL;
            //现在，让尾节点和头节点的next相连
            last->next = first ->next;
            //让头结点指向尾节点
            first->next = last;
            //更新头结点的操作，然后进行下一次操作
            first = first->next->next;
        }
    }
};

第二种，把链表一分二，拉链法

//这种方法很巧妙，我虽然想到了拉链法，但我的出发点是建立两个链表，然后拉链法都取一半
//其实只要再向前想一部就好了，可以先利用快慢节点找到链表的中间位置，然后砍断
//再反转后半链表，形成新的链表
//然后继续拉链法
class Solution {
public:
    ListNode* reverse(ListNode *p){
        if(p->next==NULL) return p;
        ListNode *p3=p->next;
        ListNode *p2=reverse(p->next);
        p3->next=p;
        p->next=NULL;
        return p2;
    }

    void reorderList(ListNode* head) {
        ListNode *fast = head;
        ListNode *slow = head;
      	//这个判断条件一定要写
        if(!head||!head->next||!head->next->next) return;
        // 利用快慢节点
        //当偶数时，fast最终是NULL，slow 最后是一半之前的那个节点
        //当奇数时，fast最终是最后一个节点，slow正好指向正中间
       while(fast&&fast->next)
        {
            fast=fast->next->next;
            slow = slow->next;
        }
        //fast节点没有利用价值，新链表是从慢节点的下一个节点开始的
        ListNode*head2 = slow->next;
        //这一句很重要，标志着一分为二
        slow->next = NULL;
        //对新链表进行反转
        head2 = reverse(head2);
        //因为是void操作，所以要保留head，用迭代器操作
        ListNode *p1 = head,*p2 = head2;        
        //当有一方指向NULL，就说明操作结束了
        while(p1&&p2)
        {
	// 		需要建立两个临时节点
            ListNode *tempH1 = p1->next;
            ListNode *tempH2 = p2->next;
            p1->next = p2;
            p2->next = tempH1;、
           //更新两个节点位置
            p1 = tempH1;
            p2 = tempH2;
        }
    }
};