数据结构链表题集

题目一：113 · 删除排序链表中的重复数字（二） - LintCode

思路：创建哨兵位头结点，原地删除

class Solution {
public:
    /**
     * @param head: head is the head of the linked list
     * @return: head of the linked list
     */

    //带哨兵位的删除方法
    ListNode* deleteDuplicates(ListNode *head) {
    //创建哨兵位
        ListNode* node=new ListNode(-1);
        node->next=head;
        //创建pre存放前指针
        ListNode* pre=node;
        //创建比较指针
        ListNode* cur=node->next;
        while(cur)
        {
            //创建标记值
            bool flag=false;
            while(cur->next&&cur->val==cur->next->val)
            {
                flag=true;
                cur=cur->next;
            }
            if(flag)
            {
                pre->next=cur->next;
                //考虑到cur->next==NULL的情况，所以
                //cur=cur->next而不是cur=cur->next->next
                cur=cur->next;
            }
            else
            {
                pre=cur;
                cur=cur->next;
            }
        }
        return node->next;
    }
};

题目二：36 · 翻转链表（二） - LintCode

思路一：反转m到n的链表，然后在将链表全部串联

需要注意特殊情况：

• 如果m==n就直接返回原来的链表
• 如果m==1时，反转返回的head发生改变

class Solution {
public:
    ListNode* reverseBetween(ListNode *head, int m, int n) {
        if(m==n||head==NULL)
            return head;
        int cnt=1;
        ListNode* ls1=head,ls2=head;
        while(cnt<m-1)
        {
            ls1=ls1->next;
            ls2=ls2->next;
            cnt++;
        }
        while(cnt<n-1)
        {
            ls2=ls2->next;
            cnt++;
        }
        ListNode* next1,res;
        ListNode* next2=ls2->next->next;
        if(m==1)
        {
            next1=ls1;
            res=reverse(ls1,ls2->next);
            head=res;
            while(res!=next1)
            {
                res=res->next;
            }
            res->next=next2;
        }
        else
        {
            next1=ls1->next;
            res=reverse(ls1->next,ls2->next);
            ls1->next=res;
            while(res!=next1)
            {
                res=res->next;
            }   
            res->next=next2;
        }
        return head;
    }
    //反转链表
    ListNode* reverse(ListNode* ltnd1,ListNode* ltnd2)
    {
        ListNode* tmp=NULL;
        while(ltnd1!=ltnd2)
        {
            ListNode* newnode=ltnd1;
            ListNode* next=ltnd1->next;
            newnode->next=tmp;
            tmp=newnode;
            ltnd1=next;
        }
        ListNode* newnode=ltnd1;
        newnode->next=tmp;
        tmp=newnode;
        return tmp;
    }
};

思路二：创建数组，第一次遍历将m到n的数据全部存放在数组中；第二次遍历改变原结点的值 。

class Solution {
public:
    ListNode* reverseBetween(ListNode *head, int m, int n) {
        if(m==n||head==NULL)
            return head;
        vector<int> nums;
        int index=1,i=0;
        ListNode* cur=head;
        //第一次遍历
        while(cur)
        {   
            if(index>=m&&index<=n)
            {
                nums.push_back(cur->val);
            }
            index++;
            cur=cur->next;
        }
        //第二次遍历
        index=1;
        cur=head;
        while(cur)
        {
            if(index>=m&&index<=n)
            {
                cur->val=nums[nums.size()-1-i];
                i++;
            }   
            index++;
            cur=cur->next;
        }
        return head;
    }
};

题目三：96 · 链表划分 - LintCode

思路：创建两个带哨兵位的链表；遍历一次链表，分别把小于x和大于等于x的结点存入两个链表中。最后将链表串接在一起

class Solution {
public:
    ListNode* partition(ListNode *head, int x) {
        //创建两个链表，一个存储大于x的数
        //另一个存储小于x的数
        //创建两个带哨兵位的链表
        ListNode* leftnum=new ListNode(0);
        ListNode* rightnum=new ListNode(0);
        ListNode* left=leftnum;
        ListNode* right=rightnum;
        while(head)
        {
            if(head->val<x)
            {
                left->next=head;
                left=head;
            }
            else
            {
                right->next=head;
                right=head;
            }
            head=head->next;
        }
        left->next=rightnum->next;
        right->next=NULL;
        return leftnum->next;
    }
};

题目四：LintCode 炼码

思路：在链表中实现快速排序

class Solution {
public:
	//在链表中实现快速排序
    ListNode* sortList(ListNode *head) {
	    if(head==NULL||head->next==NULL)
	    	return head;
		ListNode* fast=head;
		ListNode* slow=head;
		while(fast->next&&fast->next->next)
		{
			fast=fast->next;
			fast=fast->next;
			slow=slow->next;
		}
		ListNode* mid=slow->next;
		//拆解位两个链表
		slow->next=NULL;
		ListNode* ls1=sortList(head);
		ListNode* ls2=sortList(mid);
		//归并排序
		ListNode* res=merge(ls1,ls2);
		return res;
    }
    ListNode* merge(ListNode*list1,ListNode* list2)
    {
	    if(list1==NULL)	return list2;
	    if(list2==NULL) return list1;
	    //归并
	    ListNode* Head;
	    ListNode* cur;
	    if(list1->val<list2->val)
	    {
		    Head=list1;
		    list1=list1->next;
	    }else{
		    Head=list2;
		    list2=list2->next;
	    }
	    cur=Head;
	    while(list1&&list2)
	    {
		    if(list1->val<list2->val)
		    {
			    cur->next=list1;
			    cur=cur->next;
			    list1=list1->next;
		    }else
		    {
			    cur->next=list2;
			    cur=cur->next;
			    list2=list2->next;
		    }
	    }
	    if(list1)	cur->next=list1;
	    if(list2)	cur->next=list2;
	    return Head;
    }
};

题目五：LintCode 炼码

class Solution {
public:
    //双指针,将结点的地址全部存储在一个数组中
    void reorderList(ListNode *head) {
        if(head==NULL)  return ;
        vector<ListNode*> nodes;
        ListNode* cur=head;
        while(cur)
        {
            nodes.push_back(cur);
            cur=cur->next;
        }
        int left=0;
        int right=nodes.size()-1;
        cur=head;
        while(left<right)
        {   
            nodes[left]->next=nodes[right];
            nodes[right--]->next=nodes[++left];
        }
        nodes[left]->next=NULL;
    }
};

题目六：LintCode 炼码

思路：快慢指针

class Solution {
public:
    bool hasCycle(ListNode * head) {
	    if(head==NULL)	return false;
	    ListNode* fast=head;
	    ListNode* slow=head;
	    while(fast->next&&fast->next->next)
	    {
		    fast=fast->next;
		    fast=fast->next;
		    slow=slow->next;
		    if(fast==slow)
		    {
			    return true;
		    }
	    }
	    return false;
    }
};

题目7：170 · 旋转链表 - LintCode

class Solution {
public:
    ListNode* rotateRight(ListNode *head, int k) {
	    if(head==NULL||k==0)	return head; 
	    int Len=Listlen(head);
	    int step=k%Len;
	    ListNode* cur=head;
	    vector<ListNode*> nodes;
	    while(cur)
	    {
		    nodes.push_back(cur);
		    cur=cur->next;
	    }
	    cur=head;
	    ListNode* tmp1=reverse(cur,nodes[nodes.size()-1-step]);
	    ListNode* tmp2=reverse(nodes[nodes.size()-step],nodes[nodes.size()-1])
	    (nodes[0])->next=tmp2;
	    ListNode* res=reverse(nodes[nodes.size()-1-step],nodes[nodes.size()-step]);
	    return res;
    }
    ListNode* reverse(ListNode* list1,ListNode* list2)
    {
	    ListNode* Head=NULL;
	    ListNode* tmp=
	    while(list1!=list2)
	    {
		    ListNode* newcode=list1;
		    newcode->next=Head;
		    Head=newcode;
		    list1=list1->next;
	    }
		ListNode* newcode=list1;
		newcode->next=Head;
		Head=newcode;
		return Head;
    }
    int Listlen(ListNode* head)
    {
	    int res=0;
	    while(head)
	    {
		    res++;
		    head=head->next;
	    }
	    return res;
    }
};

题目八：104 · 合并k个排序链表 - LintCode

思路：使用优先队列

struct compare {
    bool operator()(const ListNode* l, const ListNode* r) {
        return l->val > r->val;
    }
};
class Solution {
public:

    ListNode *mergeKLists(vector<ListNode *> &lists) {
        if(lists.size()==0) return NULL;
        //创建优先队列
        priority_queue<ListNode* , vector<ListNode *>, compare> pq;
        for(auto i:lists)
        {
            if(i) pq.push(i);
        }
        ListNode * res = new ListNode(-1);
        ListNode * tail =res;
        while(!pq.empty())
        {
            ListNode* newnode=pq.top();
            pq.pop();
            tail->next=newnode;
            tail=newnode;
            if(newnode->next)
            {
                pq.push(newnode->next);
            }
        }
        return res->next;
    }
};