链表相关题目-leetcode简单

时间：2019-10-20 00:05:31 阅读：87 评论：0 收藏：0 [点我收藏+]

1. 合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

方法一、利用递归思想

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1==nullptr)
            return l2;
        if(l2==nullptr)
            return l1;
        
        if(l1->val < l2->val){
            l1->next = mergeTwoLists(l1->next,l2);
            return l1;
        }else{
            l2->next = mergeTwoLists(l2->next,l1);
            return l2;
        }
        
    }
};

方法二、迭代

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* newHead = new ListNode(-1);
        ListNode* p = newHead;
        while(l1!=nullptr && l2!=nullptr){
            if(l1->val <= l2->val){
                p->next = l1;
                l1 = l1->next;
            }else{
                p->next = l2;
                l2 = l2->next;
            }
            p = p->next;
        }
        
        p->next = (l1!=nullptr)? l1:l2;
        return newHead->next;
        
    }
};

2. 删除排序链表中的重复元素

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

方法一、由于要删除元素，因此要保存要删除元素的前一个结点

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(head==nullptr)
            return head;
        ListNode* pre = head;
        ListNode* curr = pre->next;
        while(curr){
            while(curr && pre->val == curr->val){
                ListNode* tmp = curr;
                curr = curr->next;
                pre->next = curr;    
                tmp = nullptr;  //清除野指针
            }
            pre = pre->next;
            if(pre)
                curr = pre->next;
            else
                curr = nullptr;
        }
        return head;
    }
};

3. 环形链表

给定一个链表，判断链表中是否有环。

方法一、快慢指针

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head==nullptr)
            return false;   //注意空链表，认为是没有环的
        
        ListNode *slow = head;
        ListNode *fast = head;
        while(fast){
            ListNode *tmp = fast->next;
            if(tmp){
                fast = tmp->next;
            }else{
                return false;
            }
                
            slow = slow->next;
            if(fast==slow)
                return true;
            
        }
        return false;
    }
};

方法二、哈希表

通过检查一个结点此前是否被访问过来判断链表是否为环形链表。常用的方法是使用哈希表

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head==nullptr)
            return false;
        
        ListNode *curr=head;
        set<ListNode*> ss;  //注意存的类型是ListNode*
        while(curr){
            if(ss.find(curr)!=ss.end()){ //存在
                return true;
            }else{
                ss.insert(curr);
                curr = curr->next;
            }
        }
        return false;
        
    }
};

方法三、反转链表（唯一的问题是破坏了原始链表）

环形链表中，环形会死循环没办法判断边界条件，因此我们我们每遍历一个链表就把后面的指向前面的，这样环形要再次循环时会反方向走，最后他会回到头节点，从而循环结束。
环形初始情况：

技术分享图片

倒置后：

技术分享图片

没有环形就是普通链表的倒置。
所以最后只要判断倒置后的首节点是不是head节点，是则true，不是则false。
时间复杂度最坏是2n（相当于从最后再来一次），即O（n），空间上只用了三个指针即O（1）。

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null)return false;
        if(head.next==head)return true;
        if(head.next==null)return false;
        ListNode p=head.next,q=p.next,x;
        head.next=null;
        for(x=head,p.next=x;q!=null;p.next=x,x=p,p=q,q=q.next);//倒置整个链表
        if(p==head)return true;//如果回到头节点说明存在环，不是则不存在环
        else return false;
    }
}