[数据结构与算法]专题复习二：链表（2）

leetcode?86. 分隔链表

首先将链表分隔为比目标值小的一段和比目标值大的一段

需要四个指针

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        if(!head) return nullptr;
        //不能直接让smallHead 或者 bigHead直接等于head 原因是不确定head-》val与x的大小关系
        ListNode* smallHead = new ListNode(0);
        ListNode* smallTail = smallHead;
        ListNode* bigHead = new ListNode(0);
        ListNode* bigTail = bigHead;
        while(head)
        {
            if(head->val < x)
            {
                smallTail->next = head;
                smallTail = smallTail->next;
            }
            else
            {
                bigTail->next = head;
                bigTail = bigTail->next;
            }
            head = head->next;
        }
        bigTail->next = nullptr;
        smallTail->next = bigHead->next;
        return smallHead->next;

    }
};

leetcode??234. 回文链表

利用辅助栈，首先将链表节点中的元素依次压入栈中，然后在依次出栈，与链表前面比较

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(!head) return false;
        ListNode* temp = head;
        stack<int> a;
        int len = 0;//用来记录 链表的长度
        //将节点中的值压入栈中
        while(temp)
        {
            a.push(temp->val);
            len++;
            temp = temp->next;
        }
        //因为只需要比较链表中一半即可，因此len/2
        len >> 1;//即len/2
        while(len--)
        {
            if(head->val != a.top())
            {
                return false;
            }
            a.pop();
            head = head->next;
        }
        return true;

    }
};

leetcode?两两交换链表中的节点

方法一：利用迭代的方法， 两两交换节点中的值来达到 交换节点的效果

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(!head) return nullptr;
        ListNode* temp = head;
        while(temp&&temp->next)
        {
            //交换相邻两个节点中的值
            int first = temp->val;
            temp->val = temp->next->val;
            temp->next->val = first;
            //往后移动两个节点
            temp = temp->next->next;
        }
        return head;
    }
};

方法二：利用递归的方法

递归的三个要素： （1）终止条件 （2）调用自身 （3）返回值

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(!head || !head->next) return head;//终止条件
        ListNode * third = swapPairs(head->next->next); 
        //将前面的两个节点互相调换 并指向third       
        ListNode* second = head->next;
        second->next = head;
        head->next = third;
        return second;
    }
};

leetcode141. 环形链表

方法一：利用快慢指针，slow和fast? ?fast = fast->next->next? slow = slow->next

fast的速度是slow的两倍，如果链表存在环，那么它们肯定会相遇

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *slow = head;
        ListNode *fast = head;
        while(fast && fast->next) //这里只需要关注 fast即可  
        { 
            fast = fast->next->next;
            if(!fast) return false;
            slow = slow->next;
            if(slow==fast) //说明fast和slow相遇了
            {
                return true;
            }
        }
        return false;
    }
};

方法二： 利用set set的底层实现是二叉搜索树，因此，其搜索效率更高

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(!head) return false;
        set<ListNode*> a;
        while(head)
        {
            if(a.find(head)!= a.end()) //说明set中已经存在该节点，说明链表中存在环
            {
                return true;
            }
            a.insert(head);
            head = head->next;
        }
        return false;
    }
};

leetcode142. 环形链表 II

方法一：利用快慢指针

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {

        ListNode* fast = head;
        ListNode* slow = head;
        while(fast && fast->next)
        {
            fast = fast->next->next;
            if(!fast) return NULL;
            slow = slow->next;
            if(slow == fast)//首先找到fast和slow相遇的点
            {
                while(head != slow) //
                {
                    head = head->next;
                    slow = slow->next;
                }
                return slow;
            }
        }
        return NULL;
        
    }
};

上述题目同样可以利用set，但是其效率较低，不建议采用。