华为OJ——从单向链表中删除指定值的节点

题目描述

　　输入一个单向链表和一个节点的值，从单向链表中删除等于该值的节点，删除后如果链表中无节点则返回空指针。 链表结点定义如下： 　　struct ListNode 　　{ 　　　　int m_nKey; 　　　　ListNode* m_pNext; 　　};

详细描述： 本题为考察链表的插入和删除知识。 链表的值不能重复 构造过程，例如 1 -> 2 3 -> 2 5 -> 1 4 -> 5 7 -> 2 最后的链表的顺序为 2 7 3 1 5 4 删除 结点 2 则结果为 7 3 1 5 4

输入描述:

1 输入链表结点个数 2 输入头结点的值 3 按照格式插入各个结点 4 输入要删除的结点的值

输出描述:

输出删除结点后的序列

示例1 输入 5 2 3 2 4 3 5 2 1 4 3 输出 2 1 5 4

实现代码：

思路：利用list集合的性质，获取需要插入点的位置，然后将需要插入点的位置插入到其中！

package cn.c_shuang.demo47; import java.util.ArrayList; import java.util.Scanner; /** * 从单向链表中删除指定值的节点 * @author Cshuang * */ public class Main{ public static void main(String[] args){ Scanner in = new Scanner(System.in); while(in.hasNextInt()){ int num = in.nextInt(); int firstNode = in.nextInt(); ArrayList<Integer> list = new ArrayList<Integer>(); list.add(firstNode); for(int i=0;i<num-1;i++){ int Node1 = in.nextInt(); //要插入的节点 int Node2 = in.nextInt(); //插入在哪个节点之后 int index = list.indexOf(Node2); list.add(index+1,Node1); } Object deleteNode = in.nextInt(); list.remove(deleteNode); for(int i=0;i<list.size()-1;i++){ System.out.print(list.get(i)+" "); } System.out.println(list.get(list.size()-1)+" "); } in.close(); } }

另解：

import java.util.*; public class Main { private static void insert(ListNote head,int key,int position) { ListNote temp=head; while(temp.key!=position) { temp=temp.nextNote; } ListNote p=new ListNote(key); p.nextNote=temp.nextNote; temp.nextNote=p; } private static void delete(ListNote head,int deleteKey) { ListNote temp=head; while(temp.nextNote.key!=deleteKey) { temp=temp.nextNote; } ListNote k=temp.nextNote; temp.nextNote=k.nextNote; } public static void main(String[] args) { // TODO Auto-generated method stub Scanner input=new Scanner(System.in); while(input.hasNext()) { int num=input.nextInt(); ListNote head=new ListNote(input.nextInt()); for(int i=1;i<num;i++) { int key=input.nextInt(); int position=input.nextInt(); insert(head,key,position); } int deleteKey=input.nextInt(); delete(head,deleteKey); StringBuilder strbd=new StringBuilder(); while(head!=null) { strbd.append(head.key+" "); head=head.nextNote; } System.out.println(strbd.toString()); } input.close(); } } class ListNote { int key; ListNote nextNote=null; public ListNote(int key) { this.key=key; } }