基础数据结构--链表的练习

单链表和双链表反转

<pre>

/**

* @author Java和算法学习--周一 */

public class ReverseNode {

    public static class Node {

        public int value;

        public Node next;

        public Node(int value) {

            this.value = value;

        }

    }

    public static class DoubleNode {

        public int value;

        public DoubleNode last;

        public DoubleNode next;

        public DoubleNode(int value) {

            this.value = value;

        }

    }

    /**

    * 单链表反转

    * a  ->  b  ->  c  ->  null

    * c  ->  b  ->  a  ->  null

    *

    * @return 返回头节点    */

    public static Node reverseNode(Node head) {

        Node pre = null;

        Node next = null;

        while (head != null) {

            next = head.next;

            head.next = pre;

            pre = head;

            head = next;

        }

        return pre;

    }

    public static DoubleNode reverseDoubleNode(DoubleNode head) {

        DoubleNode pre = null;

        DoubleNode next = null;

        while (head != null) {

            next = head.next;

            head.next = pre;

            head.last = next;

            pre = head;

            head = next;

        }

        return pre;

    }

}

</pre>

核心点:

(1)单链表:

拿到next节点,修改当前节点的next节点,拿到pre节点,当前节点后移

(2)双链表:

拿到next节点,修改当前节点的next、last节点,拿到pre节点,当前节点后移


单链表删除指定的值

/**
 * @author Java和算法学习--周一 */
public class DeleteNodeValue {

    public static class Node {
        public int value;
        public Node next;

        public Node(int value) {
            this.value = value;
        }
    }

    public static Node removeValue(Node head, int num) {
        while (head != null) {
            if (head.value != num) {
                break;
            }
            head = head.next;
        }

        Node pre = head;
        Node cur = head;
        while (cur != null) {
            if (cur.value == num) {
                pre.next = cur.next;
            } else {
                pre = cur;
            }
            cur = cur.next;
        }

        return head;
    }

}

核心点:

1)找到不需要删除值的节点作为头节点(最后返回此头节点

2)标记pre和cur节点

3)从cur开始挨个遍历剩下的节点

    如果cur节点的值等于要删除的值,则修改pre节点的next节点;

    如果cur节点的值不是要删除的值,则将pre节点修改为cur节点。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容