MENU

数据结构(二)单链表 - 基础

July 31, 2018 • Code

前言:收集了一些关于单链表的题目,并自己用 Java 实现了下。

单链表节点实现

节点中主要包括:

  • data:节点保存数据
  • next:下一节点指针
/**
 * 单链表节点
 *
 * @author kbrx93
 */
public class Node<T> {

    // 变量用 public 简化操作

    /**
     * 存储的数据
     */
    public T data;

    /**
     * 下一节点指针
     */
    public Node next;

    public Node(T data, Node next) {
        this.data = data;
        this.next = next;
    }

    public Node(T data) {
        this(data, null);
    }

    /**
     * 生成指定长度单链表,链表数据为对应索引值
     * @param len 指定链表长度
     * @return 生成链表头节点
     */
    public static Node generate(int len) {
        Node<Integer> head = new Node<>(0);
        Node<Integer> now = head;
        for (int i = 1; i < len; ++i) {
            Node<Integer> temp = new Node<>(i);
            now.next = temp;
            now = temp;
        }
        return head;
    }

    /**
     * 根据传入的节点遍历输出链表节点
     * @param head 头结点
     */
    public static void printNode(Node head) {
        if (head == null) return;
        while (head != null) {
            System.out.println(head.data);
            head = head.next;
        }
    }

    /**
     * 显示传入单个结点
     * @param node 结点
     */
    public static void printNodeOne(Node node) {
        if (node == null) return;
        System.out.println(node.data);
    }
    /**
     * 返回传入节点副本
     * @param node
     * @return
     */
    public static Node copyNode(Node node) {
        return new Node<>(node.data, node.next);
    }
}

为了方便也在 Node 中提供了一些工具方法。

从尾到头打印链表

主要包括:

  • 不改变链表结构:栈
  • 改变链表结构,将链表逆序后打印
    • 循环
    • 递归

不改变链表结构

将链表节点依旧压入栈,再从栈中弹出并打印即可完成从尾到头打印节点。

/**
 * 用栈实现从尾到头打印链表,不改变结构
 *
 * @author kbrx93
 */
public class PrintFromTailByStack {

    public static void execute(Node head) {
        Stack<Node> stack = new Stack<>();
        // 将链表压栈
        while (head != null) {
            stack.push(head);
            head = head.next;
        }
        //弹栈输出
        while (stack.size() > 0) {
            System.out.println(stack.pop().data);
        }
    }

    // 测试
    public static void main(String[] args) {
        Node head = Node.generate(10);
        System.out.println("------------ 1. 生成的链表 ------------");
        Node.printNode(head);
        System.out.println("------------ 2. 逆序输出链表 ------------");
        execute(head);
        System.out.println("------------ 3. 逆序输出后的链表(验证没有改变结构) ------------");
        Node.printNode(head);
    }
}

改变链表结构

除了上面利用栈的方式逆序打印,还可以直接将链表逆序后打印,具体实现有循环及递归两种。

循环方式

  • 代码实现
/**
 * 用循环实现从尾到头打印链表,改变链表结构
 * @author kbrx93
 */
public class PrintFromTailByCycle {

    public static void execute(Node head) {
        Node pre = null;
        Node now = head;

        while (head.next != null) {
            head = head.next;
            now.next = pre;
            pre = now;
            now = head;
        }
        // 将最后的结点连起来
        head.next = pre;
        // 打印
        Node.printNode(head);
    }

    public static void main(String[] args) {
        execute(Node.generate(10));
    }
}
  • 大体流程:

递归方式

  • 代码实现
/**
 * 用递归实现从尾到头打印链表,改变链表结构
 * @author kbrx93
 */
public class PrintFromTailByRecursion {

    public static Node execute(Node head) {
        if (head == null || head.next == null) return head;
        // 将最尾节点「传递上去」,作为逆序后链表的头结构
        Node newHead = execute(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    public static void main(String[] args) {
        Node head = Node.generate(10);
        System.out.println("------------ 1. 生成的链表 ------------");
        Node.printNode(head);
        Node execute = execute(head);
        System.out.println("------------ 2. 逆序后的链表 ------------");
        Node.printNode(execute);
    }
}
  • 大体流程

删除一个无头节点单链表的非尾节点

传入一个指向单链表节点(非尾节点)的指针,要求删除此节点。

采用的方法为「狸猫换太子」,将当前需要被删除节点的下一节点数据复制到当前节点,在链表中删除下一节点。

  • 过程

  • 代码
/**
 * 删除传入指针节点
 * @author kbrx93
 */
public class DeleteCurrentNode {

    public static void execute(Node delNode) {
        assert (delNode.next !=null): "尾结点无法删除";
        Node nextNode = delNode.next;
        delNode.data = nextNode.data;
        delNode.next = nextNode.next;

        // 冗余操作,help GC
        nextNode.next = null;
        nextNode = null;
    }

    public static void main(String[] args) {
        Node head = Node.generate(5);
        System.out.println("------------ 1. 生成的链表 ------------");
        Node.printNode(head);
        execute(head.next.next);
        System.out.println("------------ 2. 删除指定结点后的链表 ------------");
        Node.printNode(head);
    }
}

尾结点无法用此方法删除,所以要排除。

在无头节点单链表的非头结点一个节点前插入一个节点

与上面删除节点类似,都是采用置换法

  • 过程

  • 代码
public class InsertBeforeCurrentNode {

    public static void execute(Node indexNode, Node insertNode){
        indexNode.next = Node.copyNode(indexNode);
        indexNode.data = insertNode.data;
    }

    public static void main(String[] args) {
        Node head = Node.generate(5);
        System.out.println("------------ 1. 生成的链表 ------------");
        Node.printNode(head);
        execute(head.next.next, new Node<>(10));
        System.out.println("------------ 2. 插入指定结点后的链表 ------------");
        Node.printNode(head);
    }
}

单链表实现约瑟夫环

约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知 n 个人(以编号 1,2,3...n分别表示)围坐在一张圆桌周围。从编号为 k 的人开始报数,数到 m 的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。最后出列的人为胜利者。

用循环单链表实现约瑟夫环,求胜利者编号

public class JosephBySingleChain {

    public static Node execute(Node head, int n) {
        if (head == null || n <= 0) return null;
        // 将单链表变成循环单链表
        Node now = head;
        while (now.next != null) now = now.next;
        now.next = head;
        now = head;
        while (now.next != now) {
            // 循环链表中还剩 2 个及以上节点
            int count = n;
            while (--count > 0) {
                now = now.next;
            }
            // 此时 now 指向要出列节点的前一个节点
            Node nextNode = now.next;
            now.data = nextNode.data;
            now.next = nextNode.next;

            // help GC
            nextNode.next = null;
            nextNode = null;
        }
        now.next = null;
        return now;
    }

    public static void main(String[] args) {
        Node generate = Node.generate(2);
        Node execute = execute(generate, 2);
        Node.printNode(execute);
    }
}

合并两个有序链表,合并后依然有序

递归版

/**
    * 递归版
    * @param l1
    * @param l2
    * @return
    */
public static Node executeByRecursion(Node<Integer> l1, Node<Integer> l2) {
    Node newNode = null;
    if (l1 == null) return l2;
    else if (l2 == null) return l1;
    else {
        if (l1.data > l2.data){
            newNode = l2;
            newNode.next = executeByRecursion(l1, l2.next);
        } else {
            newNode = l1;
            newNode.next = executeByRecursion(l1.next, l2);
        }
    }
    return newNode;
}

循环版

// 循环版
public static Node executeByCycle(Node<Integer> l1, Node<Integer> l2) {
    if (l1 == null) return l2;
    else if (l2 == null) return l1;
    else {
        Node head, now;
        if (l1.data <= l2.data) {
            head = l1;
            l1 = l1.next;
        } else {
            head = l2;
            l2 = l2.next;
        }
        now = head;
        while (l1 != null && l2 != null) {
            if (l1.data <= l2.data) {
                now.next = l1;
                l1 = l1.next;
            } else {
                now.next = l2;
                l2 = l2.next;
            }
            now = now.next;
        }
        if (l1 != null){
            now.next = l1;
        } else {
            now.next = l2;
        }
        return head;
    }
}

查找单链表的中间节点,要求只能遍历一次链表

采用快慢指针的方法,每次移动一个指针走两步,一个指针走一步,当快指针走到链表尾端时,慢指针所指结点即为中间节点。

/**
 * 查找中间结点
 * @param head
 * @return
 */
public static Node execute(Node head) {
    Node fast, slow;
    fast = slow = head;
    
    while (fast.next != null && fast.next.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    slow.next = null;
    return slow;
}

查找单链表的倒数第k个节点,要求只能遍历一次链表

采用两个指针,一个从第 k 个节点出发,一个从开始处出发,两个指针每次走一步,当前面的指针到达结尾时,后面的指针所指结点即为所求结点。

注意判断链表节点个数是否有 k 个。

/**
 * 查找倒数第 k 个节点
 * @param head
 * @return
 */
public static Node execute2(Node head, int k) {
    if (k < 0) return null;
    Node fast = head;
    Node slow = head;
    int n = k;
    while (--k > 0 && fast.next != null){
        fast = fast.next;
    }
    // 链表长度不足 k 步
    if (k > 0) return null;
    else {
        while (fast.next != null) {
            // 同时步进
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}
Archives QR Code
QR Code for this page
Tipping QR Code
Leave a Comment