資訊專欄INFORMATION COLUMN
摘要：題目描述刪除鏈表中等于給定值的所有節(jié)點。示例輸入輸出非遞歸解法思路遍歷鏈表，找出每個待刪除節(jié)點的前一個節(jié)點。特殊情況第一個節(jié)點就是待刪除節(jié)點時，要多帶帶操作。注意點當輸入為時，按上面的思路刪除第一個節(jié)點，剩下的鏈表的頭節(jié)點又是待刪除節(jié)點。
題目描述
刪除鏈表中等于給定值 val 的所有節(jié)點。
示例輸入: 1->2->6->3->4->5->6, val = 6非遞歸解法 思路
輸出: 1->2->3->4->5
遍歷鏈表，找出每個待刪除節(jié)點的前一個節(jié)點。
特殊情況：第一個節(jié)點就是待刪除節(jié)點時，要多帶帶操作。
注意點：當輸入為：[1,1]時，按上面的思路刪除第一個節(jié)點，剩下的鏈表的頭節(jié)點又是待刪除節(jié)點。
public ListNode removeElements(ListNode head, int val) {
while(head != null && head.val == val){
ListNode pre = head;
head = pre.next;
pre.next = null;
}
if(head == null){
return null;
}
ListNode pre = head;
while(pre.next!=null){
ListNode cur = pre.next;
if(cur.val == val){
pre.next = cur.next;
cur.next = null;
}else{
pre = pre.next;
}
}
return head;
}
使用虛擬頭結(jié)點（統(tǒng)一頭節(jié)點和其他節(jié)點的操作）簡化代碼:
private class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public ListNode removeElements(ListNode head, int val) {
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
ListNode pre = dummyHead;
while(pre.next!=null){
ListNode del = pre.next;
if(del.val == val){
pre.next = del.next;
del.next = null;
}else{
pre = pre.next;
}
}
return dummyHead.next;
}
注意：這里返回時不能直接return head;
測試用例：
public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) {
val = x;
}
// 鏈表節(jié)點的構(gòu)造函數(shù)
// 使用arr為參數(shù)，創(chuàng)建一個鏈表，當前的ListNode為鏈表頭結(jié)點
public ListNode(int[] arr){
if(arr == null || arr.length == 0)
throw new IllegalArgumentException("arr can not be empty");
this.val = arr[0];
ListNode cur = this;
for(int i = 1 ; i < arr.length ; i ++){
cur.next = new ListNode(arr[i]);
cur = cur.next;
}
}
// 以當前節(jié)點為頭結(jié)點的鏈表信息字符串
@Override
public String toString(){
StringBuilder s = new StringBuilder();
ListNode cur = this;
while(cur != null){
s.append(cur.val + "->");
cur = cur.next;
}
s.append("NULL");
return s.toString();
}
}
遞歸解法
public ListNode removeElements(ListNode head, int val) {
if(head == null){
return null;
}
head.next = removeElements(head.next, val);
if(head.val == val){
return head.next;
}else{
return head;
}
}
參考：《玩轉(zhuǎn)數(shù)據(jù)結(jié)構(gòu)》
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/77602.html
摘要：刪除鏈表中等于給定值的所有節(jié)點。鏈表的刪除操作是直接將刪除節(jié)點的前一個節(jié)點指向刪除節(jié)點的后一個節(jié)點即可。這就無需考慮頭節(jié)點是否為空是否為待刪除節(jié)點。 刪除鏈表中等于給定值 val 的所有節(jié)點。 Remove all elements from a linked list of integers that have value val. 示例: 輸入: 1->2->6->3->4->5-...
摘要：刪除鏈表中等于給定值的所有節(jié)點。鏈表的刪除操作是直接將刪除節(jié)點的前一個節(jié)點指向刪除節(jié)點的后一個節(jié)點即可。這就無需考慮頭節(jié)點是否為空是否為待刪除節(jié)點。 刪除鏈表中等于給定值 val 的所有節(jié)點。 Remove all elements from a linked list of integers that have value val. 示例: 輸入: 1->2->6->3->4->5-...
摘要：移除鏈表倒數(shù)第個元素給定一個鏈表，移除倒數(shù)第個元素，返回鏈表頭部。 移除鏈表倒數(shù)第n個元素 Remove Nth Node From End of List 給定一個鏈表，移除倒數(shù)第n個元素，返回鏈表頭部。 Given a linked list, remove the nth node from the end of list and return its head. Note:...
摘要：微信公眾號記錄截圖記錄截圖目前關(guān)于這塊算法與數(shù)據(jù)結(jié)構(gòu)的安排前。已攻略返回目錄目前已攻略篇文章。會根據(jù)題解以及留言內(nèi)容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。本許可協(xié)議授權(quán)之外的使用權(quán)限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一 目錄 不...
閱讀 2328·2021-11-24 10:33
閱讀 1392·2019-08-30 15:43
閱讀 3285·2019-08-29 17:24
閱讀 3495·2019-08-29 14:21
閱讀 2233·2019-08-29 13:59
閱讀 1746·2019-08-29 11:12
閱讀 2820·2019-08-28 18:00
閱讀 1859·2019-08-26 12:17
