网站开发学校 优帮云,云建站哪家好,阿里云的网站空间,网站建设的七夕文案删除链表节点
总结一下高频常用的删除链表结点的情况#xff0c;无论对链表进行何种操作#xff0c;都需要精确查找和精确指向。另外#xff0c;在删除链表节点时有一个很好用的技巧#xff1a;虚头结点#xff0c;将头结点的特殊性转化为一般#xff0c;在后面具体阐述…删除链表节点
总结一下高频常用的删除链表结点的情况无论对链表进行何种操作都需要精确查找和精确指向。另外在删除链表节点时有一个很好用的技巧虚头结点将头结点的特殊性转化为一般在后面具体阐述。
删除特定节点
常用方法直接模拟 关键精确找到特定节点并且将其cur.next指向cur.next.next。 由于可能删除头结点可以引入一个虚头结点dummyHead来使得操作头结点的特殊性变得一般化不用单独处理头结点就和其它节点同等对待。
Code
public static ListNode removeElements(ListNode head, int val) {ListNode dummyHead new ListNode();//虚头结点的next指向头结点headdummyHead.next head;ListNode cur dummyHead;while (cur.next ! null) {if (cur.next.val val) {//跳过一个节点指向,实现删除cur.next temp.next.next;} else {cur temp.next;}}//注意虚节点的next一定是真正的删除操作过后的链表头结点return dummyHead.next;}删除倒数第K个节点
常用方法双指针 关键引入虚头结点慢指针初始化在虚头节点快指针初始化在原来的头节点注意这里快节点是要走到null而不是它的下一个为null停止因为这里快慢指针本来就有一位差距倒也是好理解如果都初始化在虚头节点则判定快节点的下一个为null。 最后记得返回的是dummyHead.next。
Code public static ListNode removeNthFromEndByTwoPoints(ListNode head, int n) {ListNode dummyHead new ListNode(0);dummyHead.next head;ListNode fast head;ListNode slow dummyHead;while (n 0){fast fast.next;n--;}while (fast ! null) {fast fast.next;slow slow.next;}slow.next slow.next.next;return dummyHead.next;}删除重复元素
重复元素保留一个
常用方法直接模拟 关键真就直接模拟没有任何套路没有任何心机就像Bob一样。
Code
public ListNode deleteDuplicates(ListNode head) {if(head null){return head;}ListNode cur head;while(cur.next ! null){if(cur.val cur.next.val){cur.next cur.next.next;}else{cur cur.next;}}return head;}重复元素全删
常用方法直接模拟 关键注意引入虚头节点并从虚头结点开始寻找比较cur.next.val和cur.next.next.val是否相等如果相等说明这个值是重复的将其暂存。 然后再往后找并比较后面的节点值是否还为这个重复值。遇到了就将其删去指向跳过。 注意由于一下往下看了两位节点搜索要在它们都不为空的情况下进行。
Code
public ListNode deleteDuplicates(ListNode head) {if (head null) {return head;}ListNode dummy new ListNode(-1111, head);ListNode cur dummy;while (cur.next ! null cur.next.next ! null) {if (cur.next.val cur.next.next.val) {//关键在这个每一次都记录这个重复的数值int k cur.next.val;//再消去所有val为这个重复数值的节点while (cur.next ! null cur.next.val k) {cur.next cur.next.next;}} else {cur cur.next;}}return dummy.next;}
