算法题：删除链表中指定值的节点（Java实现）

ゞ浴缸里的玫瑰 2021-12-19 04:03 275阅读 0赞

去美菜网面试，第一道算法笔试题就是这个，题目很清楚，删除链表中指定值的节点，假定有这样的链表：1->2->6->3->4->5->6，现在要求删除值为6的节点，输入数组\[1,2,6,3,4,5,6\]，要求输出：\[1,2,3,4,5\]。

分析：这道题有普通的做法，就是依次遍历节点，发现了节点的值等于给定的值，就将节点删除。

但是删除节点，对于普通的链表来说，如果是头节点，还好，直接head=head.next，再依次往后遍历。这里有个极端的情况，如果头节点一直就是需要删除的节点，那么这个删除还需要做一个while循环。

另外，对于普通节点的删除，我们通常只需要将当前节点的上一个节点的next指向当前节点的next即可，所以，我们在遍历的过程中，需要两个指针，一个指向当前节点，一个指向当前节点的前一个节点。

算法代码如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlaW5pZmk_size_16_color_FFFFFF_t_70][]

另一种办法，就不是直接操作链表来做删除了，而是做了一个取巧，采用栈数据结构，将链表中不等于指定值的数据节点依次压入栈中，结束以后，再从尾到头来构建这个链表，返回头节点即可。

算法代码如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlaW5pZmk_size_16_color_FFFFFF_t_70 1][]

这道题还有一个变种，就是删除重复的节点，不是将重复的所有节点删除，而是保留第一个节点，后面如果重复，就删除。这里也给出代码：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlaW5pZmk_size_16_color_FFFFFF_t_70 2][]

这个算法的思想就是通过一个HashSet集合来保存当前已经遍历的所有节点数据，如果当前节点数据在集合中已经存在，那么就删除当前节点，如果不存在，继续遍历。

算法完整代码如下：

package com.xxx.algorithm;
    import java.util.HashSet;
    import java.util.Stack;
    public class LinkedListDemo {
    	LinkNode head;
    
    	class LinkNode{
    		int val;
    		LinkNode next;
    		public LinkNode(int val){
    			this.val = val;
    		}
    	}
    	
    	//list:1->2->6->3->4->5->6        val=6
    	//list:1->2->3->4->5           
    	//链表中删除了所有数值等于6的节点
    	public LinkNode removeElements(LinkNode head,int val){
    		//这个判断很巧妙，是用来删除头结点的
    		//因为不排除头结点是要删除的节点的可能，所以需要从头结点这里判断
    		//1、如果头结点不是要删除的节点，那么直接跳出循环
    		//2、如果头结点是要删除的节点，直接head=head.next就删除了，
    		//这个删除很简单，就是切断了头结点与下一个节点之间的指针，并且指定下一个节点为新的头结点
    		while(head!=null){
    			if(head.val!=val){
    				break;
    			}
    			head = head.next;
    		}
    		//上面的循环跳出之后，说明新的头结点不可能是要删除的
    		//因此可以不用再考虑头结点的删除问题
    		LinkNode cur = head;
    		LinkNode pre = head;
    		while(cur!=null){
    			//这个相等的判断在第一次循环时不会成立
    			//所以在第一次循环结束时,pre=head,cur=head.next
    			//pre和cur是相差了一个指针的节点，相当于cur节点的的前一个结点
    			//使用pre作为指针节点是为了删除当前(如果值满足条件)节点的
    			if(cur.val==val){
    				pre.next = cur.next;
    			}else{
    				pre = cur;
    			}
    			cur = cur.next;
    		}
    		return head;
    	}
    	
    	//这种办法是通过栈来实现的，很直观：一次遍历链表，把不等于val的节点加入栈里面，然后依次取出站里面的元素，
    	//直到最后一个元素就是链表的头节点，返回这个头节点
    	//只是不明白这里的stack.peek().next = head是什么意思。
    	public LinkNode removeElementsByStack(LinkNode head,int val){
    		Stack<LinkNode> stack = new Stack<LinkNode>();
    		while(head!=null){
    			if(head.val!=val){
    				stack.push(head);
    			}
    			head = head.next;
    		}
    		while(!stack.isEmpty()){
    			stack.peek().next = head;
    			head = stack.pop();
    		}
    		return head;
    	}
    	
    	public LinkNode removeRepeat(LinkNode head){
    		if(head==null){
    			return null;
    		}
    		HashSet<Integer> set = new HashSet<Integer>();
    		set.add(head.val);
    		LinkNode pre = head;
    		LinkNode cur = head.next;
    		while(cur!=null){
    			if(set.contains(cur.val)){
    				pre.next = cur.next;
    			}else{
    				set.add(cur.val);
    				pre = cur;
    			}
    			cur = cur.next;
    		}
    		return head;
    	}
    	
    	public void display(LinkNode head){
    		System.out.print("list:");
    		LinkNode cur = head;
    		while(cur!=null){
    			System.out.print(cur.val+"->");
    			cur = cur.next;
    		}
    		System.out.print("null");
    		System.out.println();
    	}
    	
    	public void insert(int val){
    		if(head==null){
    			head = new LinkNode(val);
    		}else{
    			LinkNode cur = head;
    			while(cur.next!=null){
    				cur = cur.next;
    			}
    			cur.next = new LinkNode(val);
    		}
    	}
    	
    	public static void main(String[] args) {
    		LinkedListDemo list = new LinkedListDemo();
    		list.insert(1);
    		list.insert(2);
    		list.insert(6);
    		list.insert(3);
    		list.insert(4);
    		list.insert(5);
    		list.insert(6);
    		list.display(list.head);
    		LinkNode head = list.removeElements(list.head, 6);
    		//LinkNode head = list.removeElementsByStack(list.head, 6);
    		//LinkNode head = list.removeRepeat(list.head);
    		list.display(head);
    	}
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlaW5pZmk_size_16_color_FFFFFF_t_70]: /images/20211218/9a29355f3e2f4c9b836eed6c699865b3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlaW5pZmk_size_16_color_FFFFFF_t_70 1]: /images/20211218/943f80fa8d594921a9f6e15786692052.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlaW5pZmk_size_16_color_FFFFFF_t_70 2]: /images/20211218/a1aa08dd0fdf4ee69d96218d14c82c4f.png