一
给定一个头结点为 head 的非空单链表,返回链表的中间结点。
如果有两个中间结点,则返回第二个中间结点。
分析
就是找中间项,但是对于链表来说,我们现在不能事先知道链表的长度,所以必须要有遍历这个过程确定链表长度,之后才能找出中间项的位置。这就包括了两个过程
1.确定链表长度
2.根据链表长度确定中间项
有两种做法
1
两重循环,一重解决1,第二重解决2
1 | int count=0; |
2
可以将两个步骤写在一个循环里面,由于单链表无法从后往前寻找,我们需要两个指针,当后面的指针停下来了后,前面的也就停下来,中间项也就找到了。
方法:快慢指针
定义两个指针fast和slow,当slow走一步时,fast走两步,这样当fast走完后,slow刚好停在中间位置
1 | while(fast!=nullptr&&fast->next!=nullptr) |
二
给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
分析
和上题一样,同样需要确定链表的长度才能得出被操作数的位置,由上题的思路,我们定义两个指针i和j,让i先走,当i和j距离了n个长度,j就可以走了,在最后,就能把倒数的n确定下来
方法1
1 | ListNode*i=head,*j=head; |
方法2
利用栈先进后出的特点,先入栈,在出n个指针,就能确定n指针的前一个是什么了
1 | stack<ListNode*>point; |
效率不高,和两重循环差别感觉没多大
本文作者: jiangyuhao
本文链接: http://example.com/2022/03/27/%E5%8F%8C%E6%8C%87%E9%92%88876%E5%92%8C19/
版权声明: 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处!