---

JZ25 合并两个排序的链表（简单）

链接 简单题
题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

输入：
{1,3,5},{2,4,6}
返回值：
{1,2,3,4,5,6}

解题思路
有递归和非递归两种思路
思路一：递归

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
//递归的解法
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        ListNode* tmp = nullptr;
        if(pHead1 == nullptr) return pHead2;
        if(pHead2 == nullptr) return pHead1;
        
        if(pHead1->val <= pHead2->val)
        {
            tmp = pHead1;
            tmp->next = Merge(pHead1->next,pHead2);
        }
        else{
            tmp = pHead2;
            tmp->next = Merge(pHead1,pHead2->next);
        }
        return tmp;
    }
};

解法二：非递归解法

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        ListNode* i = pHead1, * j = pHead2;
        if(i == nullptr) return pHead2;
        if(j == nullptr) return pHead1;
        ListNode node(-1);
        ListNode* tmp = &node;
        while(i != nullptr && j != nullptr)
        {
            if(i != nullptr && i->val <= j->val) 
            {
                tmp->next = i;
                i = i->next;
                tmp = tmp->next;
            }
            if(i == nullptr)
            {
                tmp->next = j;
                break;
            }
                
            if(j != nullptr && i->val > j->val)
            {
                tmp->next = j;
                j = j->next;
                tmp = tmp->next;
            }
            if(j == nullptr)
            {
                tmp->next = i;
                break;
            } 
        }
        return node.next;
    }
};

NC22 合并两个有序的数组（简单）

链接 简单题
题目描述


解题思路

class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        int pos = m + n - 1;
        int i = m-1,j = n-1;
        while(pos > 0 && i >= 0 && j >= 0)
        {
//             if(A[i] >= B[j])
//             {
//                 A[pos] = A[i];
//                 pos--;
//                 i--;
//             }
                
//             else{
//                 A[pos] = B[j];
//                 pos--;
//                 j--;
//             }
                
            
            A[pos--] = (A[i] >= B[j] ? A[i--] : B[j--] );
        }
        while(i >= 0)
            A[pos--] = A[i--];
        while(j >= 0)
            A[pos--] = B[j--];
    }
};

NC3 链表中环的入口节点（中等）

链接 难度:中等
描述
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。

解析
双指针法：
假设一圈相遇a+b+c+b=2(a+b) 所以a = c

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        if(pHead == nullptr || pHead->next == nullptr)
            return nullptr;
        ListNode* fast = pHead;
        ListNode* slow = pHead;
        //找到相遇的点
        while(fast != nullptr && fast->next != nullptr)
        {
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow)
                break;
        }
        //将fast指针指向头结点
        if(fast != nullptr && fast->next != nullptr)
            fast = pHead;
        else
            return nullptr;
        while(fast != slow)
        {
            fast = fast->next;
            slow = slow->next;
        }
        return fast;  //再次找到相遇点就是环的入口点
    }
};

哈希法:
遍历单链表的每个结点
如果当前结点地址没有出现在set中，则存入set中
否则，出现在set中，则当前结点就是环的入口结点
整个单链表遍历完，若没出现在set中，则不存在环

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        if(pHead == nullptr) return nullptr;
        ListNode* cur = pHead;
        
        set<ListNode*> myset;
        while(cur != nullptr)
        {
            if(myset.count(cur) != 0)
                return cur;
            myset.insert(cur);
            cur = cur->next;
        }
        return nullptr;
        
    }
};

NC50 链表中的节点每k个一组翻转（中等）

链接 难度：中等
题目描述

解析

把 k 个数压入栈中，然后弹出来的顺序就是翻转的！ 这里要注意几个问题：
第一，剩下的链表个数够不够 k 个（因为不够 k 个不用翻转）；
第二，已经翻转的部分要与剩下链表连接起来。

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* reverseKGroup(ListNode* head, int k) {
        // write code here
        if (head == nullptr || k <= 1) return head;
        ListNode* cur = head;   //cur用来标志当前的位置
        ListNode node(-1);
        ListNode* tmp = &node;  //tmp指向的是新链表
        
        stack<ListNode*> st;
        //循环原有链表
        while(cur != nullptr)
        {
            int count = 0; //计数
            //入栈操作
            while(count < k && cur)
            {
                st.push(cur);
                cur = cur->next;
                count++;
            }
            //正常的出栈操作
            while(k == count && !st.empty())
            {
                tmp->next = st.top();
                st.pop();
                tmp = tmp->next;
            }
            //最后一段的操作
            if(count != k)
            {
                tmp->next = head;  
                break;
            }
            //重置下一次操作的初始结点 
            //这个非常重要，如果没有这个，测试用例[1,2],2就通过不了，因为二者成为了闭环
            //tmp指向的一直都不是空，这时候cur为空了，所以这次结束就把tmp->next置为空
            tmp->next = cur;   
            head = cur;
        }
        return node.next;        
    }
};

NC53 删除链表的倒数第n个节点(中等)

题目描述
给定一个链表，删除链表的倒数第 nn 个节点并返回链表的头指针
例如，
给出的链表为: 1\to 2\to 3\to 4\to 51→2→3→4→5, n= 2n=2.
删除了链表的倒数第 nn 个节点之后,链表变为1\to 2\to 3\to 51→2→3→5.

备注：
题目保证 nn 一定是有效的
请给出时间复杂度为\ O(n) O(n) 的算法
解题思路
利用快慢指针

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // write code here
        if(head == nullptr && n <= 0) return head;
        ListNode* fast = head;
        ListNode* slow = head;
        //先让快慢指针保持n距离
        while(n && fast)
        {
            fast = fast->next;
            n--;
        }
        //n > 0说明链表的长度没有n大
        if(n > 0)
            return head;
        if(fast == nullptr)    //fast == nullptr倒数第n个节点刚好是第一个结点
            return head->next;
        while(fast->next != nullptr) //大部分的情况
        {
            slow = slow->next;
            fast = fast->next;
        }
        slow->next = slow->next->next;;
        return head;
    }
};