3-8（单链表相关算法习题+双链表）

主要完成了三道单链表的算法题和学习了双链表的概念及其增删改查
1、删除单链表中的重复的元素。如1-2-3-3-4-4 输出为1-2
思想：这种算法题就是遍历链表将重复的数字删除就行，定义指针n1，n2，n3，n2和n3为移动的指针，主要比较相连的数据是否相同，也就是确定相同数据的个数，n1作为n2的前一个节点，n1->next=n3;直接将n2与n3之间的元素删除，当n3为空时，遍历也就结束。但是此题需要注意：当前几个节点相同时，这时候需要改变头结点的位置；还得注意尾部都相同时n3为空的情况。
2、拷贝带有随机节点的链表。
思想：这题思想主要分为3步，一：复制链表的节点，并依次连接在原节点的后面，二：找复制节点的random节点，这也是这题的难点，但是可以放在原链表来考虑，因为原链表的random是确定的，而原链表的random的next就是拷贝节点的random。三：拆，将原链表和拷贝的链表拆开。
3、将一个无序的单链表利用插序的方法插成有序的。
思想：取下头节点当作一个独立的有序链表，遍历原链表剩下的元素，如果比独立的头节点小，就头插法插到独立的节点中去，如果大于独立头结点但小于其中的某个节点，则插到其中间位置，如果比独立节点的尾还大，就用尾插法插到其独立的尾部。总结就是头插，任意位置插，尾插。

总体来说今天这3题难度不小，考虑的东西多，并且容易错。还是得努力。

循环双向链表得增删改查
首先循环双向链表得增删得时间复杂度都为0(1);
得有个邵兵节点作为头结点，方便操作，遍历双链表时，条件为while(head->next!=head)因为头结点得下一个节点如果等于头结点意味着链表遍历完成，不再是while(head)因为没有尾指针。

更多相关文章

随机推荐