链表相关问题

链表中的倒数第k个结点

输入一个链表，输出该链表中倒数第k个结点。

思路

在牛客网上看到一个很巧妙的方法。设置两个指针p，q。其中q先移动k-1步，然后p和q一起往后移，直至q移动到链表末尾。此时p指向的元素即为倒数第k个元素。

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) { ListNode* p=pListHead; ListNode* q=pListHead; unsigned int count=0; while(p!=NULL&&count!=k-1){ p=p->next; count++; } if(p==NULL) return NULL; else{ while(p->next!=NULL){ p=p->next; q=q->next; } } return q; } };

合并两个排序的链表

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

思路1（非递归）

创建一个头结点t_head（方便返回）和一个pre指针，pre指针一开始指向头结点t_head。比较l1，l2此时指向的结点值的大小，比如此时l1->val<=l2->val，那么将l1接在pre的后面，l1后移，pre后移；l2同理。循环直到l1或l2为空，再把剩余元素接到pre后面，返回头结点t_head的下一个结点即可。

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode* t_head=new ListNode(-1); ListNode* pre=t_head; while(l1!=NULL&&l2!=NULL){ if(l1->val<=l2->val){ pre->next=l1; l1=l1->next; } else{ pre->next=l2; l2=l2->next; } pre=pre->next; } pre->next=l1==NULL?l2:l1; return t_head->next; } };

思路2（递归）

按两列表当前结点的大小关系递归两列表，借助递归栈保存之前结点的递归顺序，在递归结束返回时，按之前递归的顺序返回结点指针，最终将两链表串为一个有序的链表。

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* Merge(ListNode* pHead1, ListNode* pHead2) { if(pHead1==NULL) return pHead2; if(pHead2==NULL) return pHead1; if(pHead1->val>pHead2->val){ pHead2->next=Merge(pHead1,pHead2->next); return pHead2; } else{ pHead1->next=Merge(pHead1->next,pHead2); return pHead1; } } };

合并K个排序链表

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->4->4->5->6

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/merge-k-sorted-lists 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

之前想的是顺序遍历数组中每两个链表，两两合并。这样时间复杂度有点大$O(nk)$（其中$n$为链表长度，$k$为链表数量）。 后来看了LeetCode的题解，可以利用分治的想法，每一次合并$\frac{k}{2}$个链表，过程如下图所示。时间复杂度为$O(nlo{g}_{2}k)$（其中$n$为链表长度，$k$为链表数量）。

代码（c++）

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* merge(ListNode* l1,ListNode* l2){ ListNode* head=new ListNode(-1); ListNode* pre=head; while(l1!=NULL&&l2!=NULL){ if(l1->val<=l2->val){ pre->next=l1; l1=l1->next; } else{ pre->next=l2; l2=l2->next; } pre=pre->next; } pre->next=l1==NULL?l2:l1; return head->next; } ListNode* mergeKLists(vector<ListNode*>& lists) { if(lists.size()==0) return NULL; if(lists.size()==1) return lists[0]; int interval=1; while(interval<lists.size()){ for(int i=0;i<lists.size()-interval;i+=interval*2){ lists[i]=merge(lists[i],lists[i+interval]); } interval*=2; } return lists[0]; } };