赞
踩
笔者计划在暑假啃完JavaDS,Mysql的内容当然也会继续更
这次给读者们分享的是链表的几个比较典型的题目,关于如何手搓一个链表,笔者还在筹划中,
毕竟链表的种类也有那么多,但是在下面的题目中,只有单向链表
很明显,想要反转一个链表,就要改变他们的地址域,具体是这样 改变的,将他们地址域的值由后一个节点的地址改为前一个节点的地址,同时注意,原head节点的 地址域应为NULL,因为反转以后,他就是最后一个节点了,因此,我们需要两个临时变量
具体写法如下
- class Solution {
- public ListNode reverseList(ListNode head) {
- ListNode pre= null;
- ListNode cur=head;
- while(cur!=null)
- {
- ListNode nextnode=cur.next;
- cur.next=pre;
- pre=cur;
- cur=nextnode;
- }
- return pre;
- }
- }
具体解释如下:
cur是头节点,没什么问题,pre负责的是存储上一个节点的地址,在反转以后,head节点的地址域是空的,所以pre也就是空的
在循环中,首先定义一个临时变量存储节点原本的地址,即下一个节点的位置
然后将上一个节点的位置(pre)存在地址域,然后将pre更新为当前节点的位置,然后cur变为nextnode;
为什么不直接cur=cur.next? 因为cur.next已经被更新了,需要有一个临时变量存原本的next;
这里的题目要求返回头节点,一般来说,反转也可以这么写
- public void reverseList()
- {
- Listnode pre=null;
- Listnode cur=head;
- while(cur!=null)
- {
- Listnode nextnode=cur.next;
- cur.next=pre;
- pre=cur;
- cur=nextnode;
- }
- this.head=pre;
- }
将pre设置为新的头以后,再通过display() 遍历
也可指定节点开始反转,只要把cur设置为指定节点即可;
- public void reverseList( 指定节点 node)
- {
- Listnode pre=null;
- Listnode cur=node;
- while(cur!=null)
- {
- Listnode nextnode=cur.next;
- cur.next=pre;
- pre=cur;
- cur=nextnode;
- }
- this.head=pre;
- }
想要移除这些节点,就要改变他们前一个节点的地址域,也就是说,把他们的地址域改成下一个节点的,直接跳过需要删除的元素
比如我画的示意图
代码实现如下
-
-
- class Solution {
- public ListNode removeElements(ListNode head, int val)
- {
- ListNode shaobing = new ListNode(0);
- shaobing.next = head;
- ListNode temp = shaobing;
- while(temp.next!=null)
- {
- if(temp.next.val==val)
- {
- temp.next= temp.next.next;
- }
- else
- {
- temp=temp.next;
- }
- }
- return shaobing.next;
- }
- }
这样也就搞定了
这个就是快慢指针的套路,快指针走两步,慢指针一步,然后找到中间节点
- class Solution {
- public ListNode middleNode(ListNode head) {
- if (head == null) {
- return null;
- }
- ListNode slow = head;
- ListNode fast = head;
- // 快指针每次移动两步,慢指针每次移动一步
- while(fast!=null&& fast.next!=null)
- {
- slow=slow.next;
- fast=fast.next.next;
- }
- return slow;
- }
- }
条件就是 快指针的本身不为空,以及它的下一步不能为空
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。