算法－第四版－练习1.3.26解答

问题

编写一个方法insertAfter()，接受一个链表和一个字符串key作为参数，删除链表中所有item域为key的结点。

解决思路

遍历链表，删除元素结点，注意别断链。复杂度O(N)。

由于使用类来封装，这里只需提供一个字符串参数即可。

代码

    public void remove(Item item)
    {
        while (first != null && item.equals(first.item))
        {
            first = first.next;
        }
        
        Node<Item> current = first;
        Node<Item> node;
        while (current != null && current.next != null)
        {
            node = current.next;
            if (item.equals(node.item))
            {
                current.next = node.next;
            }
            else
            {
                current = node;
            }
        }
    }

测试代码：

/**
 * Description : 
 * Author      : mn@furzoom.com
 * Date        : Oct 25, 2016 10:28:24 AM
 * Copyright (c) 2013-2016, http://furzoom.com All Rights Reserved.
 */
package com.furzoom.lab.algs.ch103;

/**
 * ClassName    : E10326 <br>
 * Function     : TODO ADD FUNCTION. <br>
 * date         : Oct 25, 2016 10:28:24 AM <br>
 * 
 * @version 
 */
public class E10326
{
    public static void main(String[] args)
    {
        LinkList<String> ll = new LinkList<String>();
        ll.append("a");
        ll.append("a");
        ll.append("a");
        
        ll.printList();
        
        ll.remove("b");
        System.out.println("After remove("b"): ");
        ll.printList();
       
        ll.remove("a");
        System.out.println("After remove("a"): ");
        ll.printList();
        
        ll.append("b");
        ll.append("b");
        ll.append("a");
        ll.append("a");
        ll.append("b");
        ll.append("b");
        ll.append("b");
        System.out.println("new list: ");
        ll.printList();
        
        ll.remove("b");
        System.out.println("After remove("b"): ");
        ll.printList();
         
        ll.append("b");
        ll.append("b");
        ll.append("a");
        ll.append("a");
        ll.append("b");
        ll.append("b");
        ll.append("b");
        System.out.println("another new list: ");
        ll.printList();
        
        ll.remove("a");
        System.out.println("After remove("a"): ");
        ll.printList();
        
        
    }
}

结果：

a
a
a
After remove("b"): 
a
a
a
After remove("a"): 
new list: 
b
b
a
a
b
b
b
After remove("b"): 
a
a
another new list: 
a
a
b
b
a
a
b
b
b
After remove("a"): 
b
b
b
b
b

算法－第四版－1.3 背包、队列和栈－习题索引汇总

算法－第四版习题索引汇总