LeetCode刷题总结——链表

前言

  这里记录了有关链表知识的我不会解的和我认为值得收藏的编程题目及题解，主要是为了提高自己的编程能力。希望自己勤加练习，越做越熟练。嗯，都是用C/C++实现的。

正文
一、第一题

 题目描述：

  判断给定的链表中是否有环

 扩展：
  你能给出不利用额外空间的解法么？

 题目代码：

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        
    }
};

 解题思路：

  用快慢指针解题：设置一个快指针和一个慢指针分别指向头结点，快慢指针通过循环以不同的速度走链表，快指针每次走两步，慢指针每次走一步，每走一个循环判断快指针是否与慢指针相等，若相等，则有环，否则则无环。因为，如果链表无环，慢指针永远不可能追上快指针，只有当有环时，快慢指针才能相遇。

 题解代码：

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *first,*slow;
        first=head;
        slow=head;
        while(first && first->next)
        {
            first=first->next->next;
            slow=slow->next;
            if(first==slow)
                return true;
        }
        return false;
    }
};
二、第二题

 题目描述：

  删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次

 例如：

  给出的链表为1->1->2,返回1->2.
  给出的链表为1->1->2->3->3,返回1->2->3.

 示例：

  输入
   {1,1,2}

  输出
   {1,2}

 题目代码:

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

class Solution {
public:
    /** * * @param head ListNode类 * @return ListNode类 */
    ListNode* deleteDuplicates(ListNode* head) {
        // write code here
    }
};

 解题思路：

  设置一个指针变量，指向头结点。进入循环，若前一个元素与后一个元素相等，将前一个元素的下一个元素指向后一个元素的下一个元素，若不相等指针变量指向后一个元素。

 题解代码：

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

class Solution {
public:
    /** * * @param head ListNode类 * @return ListNode类 */
    ListNode* deleteDuplicates(ListNode* head) {
        // write code here
        if(!head)
            return head;
        ListNode *h;
        h=head;
        while(h->next)
        {
            if(h->val==h->next->val)
                h->next=h->next->next;
            else
                h=h->next;
        }
        return head;
    }
};
三、第三题

 题目描述：

  将给定的链表中每两个相邻的节点交换一次，返回链表的头指针

 例如：

  给出1->2->3->4，你应该返回链表2->1->4->3。
你给出的算法只能使用常量级的空间。你不能修改列表中的值，只能修改节点本身。

 示例：

  输入
   {1,2},2

  输出
   {2}

 题目代码：

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

class Solution {
public:
    /** * * @param head ListNode类 * @return ListNode类 */
    ListNode* swapPairs(ListNode* head) {
        // write code here
    }
};

 解题思路：

  递归实现：因为是每两个相邻结点交换一次，所以把链表以两个节点为一组分组，然后设置一个指针变量指向每两个结点中的第二个节点。交换两节点位置，使前一节点指向下两个结点中的第二个一节点，而后一节点指向前一节点。从最后一组开始，一组一组实现交换，然后把交换好的结果返回给上一组，直到全部交换成功。

 题解代码：

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

class Solution {
public:
    /** * * @param head ListNode类 * @return ListNode类 */
    ListNode* swapPairs(ListNode* head) {
        // write code here
        if(!head || !head->next)
            return head;
        ListNode *h;
        h=head->next;
        head->next=swapPairs(h->next);
        h->next=head;
        return h;
    }
};
尾言

  暂时记录这么些题，以后遇到相同知识点的题会继续增加进来。

小小推荐

  烂数据爆锤算法系列：

   单链表
   循环链表
   内排序之插入算法
   内排序之交换算法
   广度、深度优先搜索例题之炸弹人

感谢阅览，希望大家多多
点赞、收藏、转发
一波三连
拜~~~