反转链表、环形链表和删除某一个节点
2020-07-08 本文已影响0人
YYFast
反转链表、环形链表和删除某一个节点
查看关于网上的一些反转链表的思路,发现步骤十分复杂,在学习了小码哥的数据结构以后,整理了一下,作为学习笔记;
链表:有一个head指针,指向链表的第一个节点;
节点ListNode: val 即节点存储的元素;next指针指向下一个节点或者null;
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
1 链表反转
1.1 思路一: 递归实现
前提条件: 我们现在能拿到的就是head也就是第一个节点
1、方法reverseList要传入head实现如下效果:
实现效果返回一个newHead指向原链表的最后一个节点;
2、递归思路关键点:当reverseList方法传入的节点是head.next的时候:
传入head.next效果最后4节点的next指向null;
代码如下:
//递归实现
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null) return head; //步骤1
ListNode newHead = reverseList(head.next); //步骤2
head.next.next = head; //步骤3
head.next = null; //步骤4
return newHead;
}
-
步骤1、递归循环结束临界条件;
- 当head == null时,应直接返回null,即head;
- 当head.next ==null时,应直接返回head;
-
步骤2、递归实现,传入head.next,实现效果如上图;
-
步骤3、将节点4,即head.next,指向head
1.2 思路二: 非递归实现
前提条件: 我们现在能拿到的就是head也就是第一个节点,所以要从第一个节点开始遍历反转,串起来;
图1 反转前通过head和newHead,及tmp将节点一个一个串起来:
图2 第一个节点被串起来代码:
//非递归
public ListNode reverseList2(ListNode head) {
ListNode newHead = null;
while (head != null) {
ListNode tmp = head.next; //注意
head.next = newHead; //步骤1
newHead = head; //步骤2
head = tmp; //步骤3
}
return newHead;
}
- 创建一个newHead指向null,这个newHead将会是反转后链表的头部;
- 步骤1、将head.next指向newHead(即第一个节点的next指向newHead);
- 步骤2、将newHead指向head(如图2所示第一个节点5就被newHead串起来了);
- 步骤3、将head指针指向下一个节点4 (循环操作)
- 注意 : 在第1步将head.next指向newHead时:因为没有指针指向后面的链表,所以后面的链表可能会被销毁,所以要先创建一个tmp指针指向head.next;
2 环形链表
image.png判断一个链表是否有环,需要用到一个思想:快慢指针
slow指针:每次循环挪动一个节点;
fast指针:每次挪动两个节点;
当slow == fast时表示有环,返回true
当fast == null 或者 fast.next == null的时候没有环,返回false
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) return false;
ListNode slow = head;
ListNode fast = head.next; //为了后面的判断第一次slow == fast不成立
while(fast != null && fast.next != null){
if(slow == fast) return true;
slow = slow.next;
fast = fast.next.next;
}
return fasle;
}
3 删除链表的某一个节点
image.png删除链表中的某一个节点,只要弄清楚思路就很简单:
- 步骤1、用让当前节点node的下一个节点的值val覆盖当前节点的值
- 步骤2、当前节点的指针指向next.next
public void deleteNode(ListNode node) {
node.val = node.next.val; //步骤1
node.next = node.next.next; //步骤2
}