表的删除就是指针的移动,将待删除节点的指针移动到下一个节点 题1:删除某个链表中给定的(非末尾)节点,你将只被给定要求被删除的节点。 虽然我们并不知道,这个节点的前一个节点时什么,但是我们知道这个节点的下一个节点是什么, 将当前要删除的节点替换为下一个节点即可
public static void deleteNode(ListNode node) {
if(node == null || node.next == null){
return;
}
ListNode next = node.next;
node.val = next.val;
node.next = next.next;
}
题:反转一个单链表 链表的反转不需要不需要创建新的对象,整个过程也就是指针的移动
if(head == null || head.next == null) {
return head;
}
// 新的节点
ListNode pre = null;
ListNode next = null;
while (head != null) {
// 首先保存待移动节点的下一个节点
next = head.next;
// 分离当前节点,并指向新的节点
head.next = pre;
// 挪动新节点的指针
pre = head;
// 挪动旧节点指针
head = next;
}
return pre;
题:两个有序链表的合并 有序链表的合并,就是将另外一个链表的节点不断插入另一个节点
if(l1 == null || l2 ==null) {
return l1 == null ? l2 : l1;
}
ListNode head = l1.val < l2.val ? l1 : l2;
ListNode cur1 = head == l1 ? l1 : l2;
ListNode cur2 = head == l1 ? l2 : l1;
ListNode pre = null ;
ListNode next = null;
while(!(cur1 == null || cur2 == null)) {
// 值比另外一个节点小,就直接遍历下一个节点
if (cur1.val <= cur2.val) {
pre = cur1;
cur1 = cur1.next;
} else {
// 将cur2的节点插入到cur1中
next = cur2.next;
pre.next = cur2;
cur2.next = cur1;
pre = cur2;
cur2 = next;
}
}
pre.next = cur1 == null ? cur2 : cur1;
return head;
if (head == null || head.next == null || head.next.next == null) {
return false;
}
ListNode step1 = head;
ListNode step2 = head;
while (step2 != null && step2.next !=null) {
step1 = step1.next;
step2 = step2.next.next;
if (step1 == step2) {
return true;
}
}
return false;
官方解答: https://leetcode-cn.com/articles/linked-list-cycle/