数据结构常见编程题小结.doc

《数据结构常见编程题小结.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1、单链表因为单链表要考虑的可能性比较少，所以单链表的题目比较简单，而且比较常考。特别要注意的是链表的数据的插入和删除，因为（没有头节点）的单链表在第一个元素之前插入和删除和最后一个元素的插入删除需要特别考虑。做题时，最好把单链表的示意图画出来，这样就很方便写代码了。常用技巧：快慢指针，拆分链表数据结构定义如下： C++Code 12345struct ListNode {     int val;//值     ListNode *next;//下一个元素     ListNode(int x) : val(x), next(NULL) {}/

2、/new初始化 };下面是一些常考的题目：（1）LinkedListCycle-判断一个链表是否有环最好的方法是时间复杂度O(n)，空间复杂度O(1)的。设置两个指针，一个快一个慢，快的指针每次走两步，慢的指针每次走一步，如果快指针和慢指针相遇，则说明有环。（如何证明，上网找找）代码实现如下： C++Code 12345678910111213//LeetCode, Linked List Cycle// 时间复杂度 O(n)，空间复杂度 O(1)class Solution{public:    bool hasCycle(ListNode *

3、head)    {        // 设置两个指针，一个快一个慢        ListNode *slow = head, *fast = head;        while (fast && fast->next)        {            slow = slow->next;            fast = fast->next->next;1415161718            if (slow == fast) return true;        }        return false;    }};

4、（1）LinkedListCycleII-链表有环，找出环的起始点当fast与slow相遇时，slow肯定没有遍历完链表，而fast已经在环内循环了n圈(1n)。假设slow走了s步，则fast走了2s步（fast步数还等于s加上在环上多转的n圈），设环长为r，则：2s=s+nrs=nr设整个链表长L，环入口点与相遇点距离为a，起点到环入口点的距离为x，则x+a=nr=(n–1)r+r=(n1)r+Lxx=(n1)r+(L–x–a)L–x–a为相遇点到环入口点的距离，由此可知，从链表头到环入口点等于n1圈内环+相遇点到环入口点，于是我们可以从he

5、ad开始另设一个指针slow2，两个慢指针每次前进一步，它俩一定会在环入口点相遇。 C++Code 12345678910111213//LeetCode, Linked List Cycle II// 时间复杂度 O(n)，空间复杂度 O(1)class Solution{public:    ListNode *detectCycle(ListNode *head)    {        ListNode *slow = head, *fast = head;        while (fast && fast->next)       

6、 {            slow = slow->next;            fast = fast->next->next;            if (slow == fast)14151617181920212223242526            {                ListNode *slow2 = head;                while (slow2 != slow)                {                    slow2 = slow2->next;       

7、             slow = slow->next;                }                return slow2;            }        }        return nullptr;    }};（1）AddTwoNumberYouaregiventwolinkedlistsrepresentingtwonon-negativenumbers.Thedigitsarestoredinreverseorderandeachoftheirnodescontainasingledigit.A

8、ddthetwonumbersandreturnitasalinkedlist.Input:(2->4->3)+(5->6->4)Out