做美食网站的特点,劳动合同模板免费,做效果图兼职的网站有哪些,网站建设规划任务书在数据结构的最高层抽象里#xff0c;只有两种结构#xff0c;数组和链表。这两种结构#xff0c;是所有其他数据结构实现的基础。队列和栈#xff0c;可以用链表和数组来实现。图#xff0c;可以用邻接表和邻接矩阵来实现#xff0c;其中#xff0c;邻接表就是链表只有两种结构数组和链表。这两种结构是所有其他数据结构实现的基础。队列和栈可以用链表和数组来实现。图可以用邻接表和邻接矩阵来实现其中邻接表就是链表邻接矩阵就是数组。树用数组实现可以实现堆用链表实现可以实现二叉树AVL树等等。所以链表的操作是掌握数据结构最基础的能力。一切数据结构的操作无非就是遍历增删查改。由于每一种数据结构有不同的特性比如数组结构不需要存储指针而链表结构需要存储指针。数据结构的增删查改就是在这些特性的基础之上来完成的。关于链表面试算法的第一块主要来学习链表这种数据结构是如何来实现删除节点的。常见的删除节点题目有删除链表中的节点_leetcode273 移除链表元素_leetcode203 删除链表的倒数第N个节点_leetcode19 删除排序链表中的重复元素_leetcode83 删除排序链表中的重复元素 II_leetcode82 1.删除链表中的节点思路分析在链表中删除一个节点node的常见方法是
找到该节点的前驱节点修改节点的next指针使其指向node的下一个节点。时间复杂度为O(1)的方法
把将要删除的node节点的值替换为它的后继节点然后删除它之后的节点即可。
但是这种方法需要保证被删除的节点不是链表末尾。
若是末尾则只能通过找到前序节点的方法来实现删除。 被删除节点不为尾结点情况下代码演示如下class Solution {public void deleteNode(ListNode toBeDeleted) { toBeDeleted.val toBeDeleted.next.val;toBeDeleted.next toBeDeleted.next.next;}
} 被删除节点可能为尾结点情况下代码演示如下public static ListNode deleteNode(ListNode head,ListNode toBeDeleted){if(headnull || toBedeleted null){return head;}// 若被删除节点为尾结点则遍历链表找到其前驱节点if(toBeDeleted.next null){ListNode curr head;while(curr.next!toBeDeleted){curr curr.next;}curr.next null;//直接删除为节点}else{toBeDeleted.value toBeDeleted.next.value;// 待删除的结点的下一个指向原先待删除引号的下下个结点即将待删除的下一个结点删除 toBeDeleted.next toBeDeleted.next.next;}//return head;}2.移除链表元素思路方法哑结点双指针
步骤设置前驱指针pre和工作指针cur来遍历数组若发现目标值则删除否则一起向前。代码class Solution {public ListNode removeElements(ListNode head, int val) {ListNode dummy new ListNode(-1);dummy.next head;ListNode pre dummy;ListNode cur head;while(cur!null){if(cur.valval){pre.next cur.next;cur cur.next;}else{precur;curcur.next;}}return dummy.next; }
}3.删除链表的倒数第N个节点思路使用两个指针首先p1指向头结点p2指向第n1个节点。
然后p1,p2两个指针同时向后移动。当p2指向尾节点时p1指向的便是倒数第n1个节点。
倒数第n1个节点为倒数第n个节点的前驱。
难点如何定位到第n个节点这个需要特别注意。使用for循环定位比使用while循环定位更易理解。巧用哑结点避免空指针等多种情况的讨论。 当不使用哑结点来进行运算时代码如下public ListNode removeNthFromEnd(ListNode head, int n) {ListNode phead;int len0;while (p!null){pp.next;len;}if(lenn)return null;if(lenn) return head.next;ListNode p1head,p2head;// p1指向第一个数需要移动n步才能指向第n1个数,此时p1与p2的距离为n。for(int i1;in;i){p1p1.next;}while (p1.next!null){p1p1.next;p2p2.next;}p2.nextp2.next.next;return head; }使用哑结点的方式代码如下class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy new ListNode(-1);dummy.next head;ListNode p1 dummy;// p1实际上为被删除节点的前驱节点即倒数第n1个节点。ListNode p2 dummy;// p2移动n步指向原链表中的第n个节点此时p1与p2之间的距离为n.for(int i1;in;i){p2 p2.next;}// p1,p2同时向后移当p2指向尾节点时p1指向倒数第n1个节点while(p2.next!null){p1p1.next;p2p2.next;}p1.next p1.next.next;return dummy.next;}
}4. 删除排序链表中的重复元素题目注意事项在链表题中需要注意的是操作链表的结点指针一定要做非空检查避免报空指针异常。思路因为输入的列表已排序
因此我们可以通过将结点的值与它之后的结点进行比较来确定它是否为重复结点。
如果它是重复的我们更改当前结点的 next 指针以便它跳过下一个结点并直接指向下一个结点之后的结点。代码如下class Solution {public ListNode deleteDuplicates(ListNode head) {ListNode cur head;while(cur!null cur.next !null){if(cur.valcur.next.val){cur.next cur.next.next;}else{cur cur.next;}}return head;}
}5. 删除排序链表中的重复元素 II题目给定一个排序链表删除所有含有重复数字的节点只保留原始链表中 没有重复出现的数字。思路和上一题相比需要在代码中实现去重操作。
哑结点双指针法。
哑结点用于记录不重复数字的头
p1指向不重复数字的最后一位p2作为工作指针向前扫描。
去重的判断条件(p2!null p2.next!null p2.val !p2.next.val)代码如下class Solution {public ListNode deleteDuplicates(ListNode head) {ListNode dumpy new ListNode(-1);ListNode p1 dumpy;ListNode p2 head;while(p2!null){if(p2!null p2.next!null p2.val p2.next.val){// 若重复则实现去重操作int temp p2.val;while(p2!nullp2.valtemp){p2p2.next;// 去重操作}}else{// 否则将不重复节点加入到新链表中。ListNode next p2.next;p2.next null; // p2和原来节点断开p1.nextp2; // 将阉割后的p2节点加到p1上p1 p2;p2 next;}}return dumpy.next;}
}总结从上述的五道链表删除题可以看出这种题目常见的技巧是使用哑结点双指针来做可以避免很多非空的判断使得代码健壮且简洁。
相关文章：
