算法练习(35): 链表的增删查改1(1.3.18-1.3.20

本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论

算法(第4版)

知识点

• 链表节点增删查改

题目

1.3.18 假设x是一条链表的某个结点且不是尾结点。下面这条语句的效果是什么？

---

1.3.18 Suppose x is a linked-list node and not the last node on the list.What is the effect of the following code fragment?

x.next = x.next.next;

Answer : Deletes from the list the node immediately following x.

分析

删除节点

答案

删除紧临在x后面的一个结点。

题目

1.3.19 给出一段代码，删除链表的尾结点，其中链表的首结点为first。

---

1.3.19 Give a code fragment that removes the last node in a linked list whose first node is first.

分析

要删除尾结点，需要找到倒数第二个结点。尾结点为node->next == null。将倒数第二个结点置为null即可。

答案

public class LinkedListExecise1<Item> {

    // 节点
    private static class Node<Item> {
        Node<Item> next;
        Item item;
    }

    public Node<Item> deleteLastNode(Node<Item> first) {
        if (first == null) {
            return null;
        }
        //current是当前遍历到的节点
        Node<Item> current = first;
        if (current.next == null) {
            first = null;
            return first;
        }
        //secondLast 倒数第二个节点
        Node<Item> secondLast = first;
        while (current.next != null) {
            //这里是引用，操作secondLast就是操作链表本身
            secondLast = current;
            current = current.next;
        }
        //这里是引用，操作secondLast就是操作链表本身
        secondLast.next = null;
        return first;
    }

    public static void main(String[] args) {

        /**
         * 创建链表
         * */
        Node<String> first = new Node<String>();
        Node<String> second = new Node<String>();
        Node<String> third = new Node<String>();
        Node<String> forth = new Node<String>();
        Node<String> fifth = new Node<String>();
        first.item = "我的";
        first.next = second;
        second.item = "名字";
        second.next = third;
        third.item = "叫";
        third.next = forth;
        forth.item = "顶级程序员不穿女装";
        forth.next = fifth;
        fifth.item = "微博:https://m.weibo.cn/p/1005056186766482";
        fifth.next = null;
        
        //删除尾节点之前
        System.out.println("原链表：\n-------");
        Node current1 = first;
        while (current1.next != null) {
            System.out.println(current1.item);
            current1 = current1.next;
        }
        System.out.println(current1.item);
        System.out.println("-------");

        LinkedListExecise1<String> linkedListExercise1 = new LinkedListExecise1<String>();
        //删除最后一个元素
        System.out.println("正在删除链表最后一个节点...");
        Node<String> resultNode = linkedListExercise1.deleteLastNode(first);
        System.out.println("删除成功");
        
        System.out.println("新链表：\n-------");
        Node current2 = resultNode;
        while (current2.next != null) {
            System.out.println(current2.item);
            current2 = current2.next;
        }
        System.out.println(current2.item);
        System.out.println("-------");
    }
}

代码索引

LinkedListExecise1.java

题目

1.3.20 编写一个方法delete()，接受一个int参数k，删除链表的第k个元素（如果它存在的话）。

---

1.3.20 Write a method delete() that takes an int argument k and deletes the kth element in a linked list, if it exists.

分析

分多种情况，当链表为空链表，当链表只有一个节点，当链表有多个节点

答案

public class LinkedListExecise2<Item> {

    private static class Node<Item> {
        Node next;
        Item item;
    }

    /**
     * 
     * @param k 第K个元素
     * @param first 链表的首节点
     * @return 新的链表
     * @throws Exception 
     */
    public Node<Item> delete(int k, Node<Item> first) throws Exception{
        if (k < 0 || first == null) return null; 
        if (k == 0) {
            first = first.next;
            return first;
        }
        Node<Item> current = first;
        while (current != null && --k != 0) {
            current = current.next;
        }
        if (k!= 0 || current.next == null || current == null) {
            throw new Exception();
        }else {
            current.next = current.next.next;
        }
        
        return first;
    }
    

    public static void main(String[] args) {
        /**
         * 创建链表
         * */
        Node<String> first = new Node<String>();
        Node<String> second = new Node<String>();
        Node<String> third = new Node<String>();
        Node<String> forth = new Node<String>();
        Node<String> fifth = new Node<String>();
        first.item = "我的";
        first.next = second;
        second.item = "名字";
        second.next = third;
        third.item = "叫";
        third.next = forth;
        forth.item = "顶级程序员不穿女装";
        forth.next = fifth;
        fifth.item = "微博:https://m.weibo.cn/p/1005056186766482";
        fifth.next = null;

        // 删除尾节点之前
        System.out.println("原链表：\n-------");
        Node current1 = first;
        while (current1.next != null) {
            System.out.println(current1.item);
            current1 = current1.next;
        }
        System.out.println(current1.item);
        System.out.println("-------");

        LinkedListExecise2<String> linkedListExercise2 = new LinkedListExecise2<String>();
        // 删除第一个元素
        int k = 4;
        System.out.println("正在删除链表第" + k + "个节点...");
        Node<String> resultNode = null;
        try {
            resultNode = linkedListExercise2.delete(k,first);
        } catch (Exception e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
        System.out.println("删除成功");

        System.out.println("新链表：\n-------");
        Node current2 = resultNode;
        while (current2.next != null) {
            System.out.println(current2.item);
            current2 = current2.next;
        }
        System.out.println(current2.item);
        System.out.println("-------");

    }

}

代码索引

LinkedListExecise2.java

视频讲解

广告

我的首款个人开发的APP壁纸宝贝上线了，欢迎大家下载。