Question

单链表和循环链表操作用什么不一样？

Answer 1

设有两个链表La＝（a1，a2，…，an）和Lb＝（b1，b2，…bm），讨论如下问题：

（1）La、Lb都是带头指针的单链表，如何实现将Lb接在La之后？时间复杂度是多少？

解答：先从La的头结点开始把指针移动到单链表的最后一个结点，即移动了La长度的结点数目，最后把Lb接在La之后，因此时间复杂度是O（n）。

（2）La、Lb都是带头结点的单循环链表，如何实现将Lb接在La之后形成一个循环链表？

时间复杂度是多少？

解答：先从La的头指针开始，把指针移动到循环链表的最后一个结点，移动了La长度的结点数目，再从Lb的头指针开始把指针移动到循环链表的最后一个结点，移动了Lb长度的结点数目，最后将Lb接在La之后还形成一个循环链表，时间复杂度为O（n＋m）。

（2）La、Lb都是带头结点、尾指针的单循环链表，如何实现将Lb接在La之后还形成一个循环链表？时间复杂度是多少？

解答：La、Lb都是带头结点、尾指针的单循环链表，仅需将La表的表尾和Lb的表头相连就形成一个循环链表，因此时间复杂度是O（1）。