链表的基本操作——反转与删除

╰半夏微凉° 2022-10-22 04:08 88阅读 0赞

# 引言 #

链表相关的问题几乎都是coding问题，以下是两个简单的链表问题。

# 一、单链表或双链表如何反转 #

## 1.1 单链表的反转操作 ##

给定一个 Node 结构：

public static class Node {
        public int value;
        public Node next;
    
        public Node(int data) {
            this.value = data;
        }
    }

这是一个单链表结构， 假设初始时，a --> b --> c --> null ：

Node a = new Node(1);
    Node b = new Node(2);
    Node c = new Node(3);
    a.next = b;
    b.next = c;
    c.next = null;

那么如何实现指针的反转，最终 c --> b --> a --> null ?

代码实现：

public static Node reverseLinkedList(Node head) {
        Node prev = null;
        Node next = null;
        while (head != null) {
            // 取得下一个Node
            next = head.next;
            // 改变当前 head 的指针，使其指向 prev
            head.next = prev;
            // 后两步是变换角色，把当前的 head 变成 prev
            prev = head;
            // 把 next 下一次循环的 head
            head = next;
        }
        // 因为最后 head 为 null 才会跳出循环，因此，需要返回 prev 元素
        return prev;
    }

测试：

public static void main(String[] args) {
        Node a = new Node(1);
        Node b = new Node(2);
        Node c = new Node(3);
        a.next = b;
        b.next = c;
        c.next = null;
    
        Node head = a;
        printNodes(head);
        Node newHead = reverseLinkedList(head);
        System.out.println("\n反转后：");
        printNodes(newHead);
    }
    
    public static void printNodes(Node head) {
        while (head != null) {
            System.out.print(head.value);
            head = head.next;
        }
    }

## 1.2 双向链表反转 ##

public class LinkedListTest2 {
    
        public static Node[] nodes = new Node[3];
    
        static {
            Node a = new Node(1);
            Node b = new Node(2);
            Node c = new Node(3);
            a.prev = null;
            a.next = b;
            b.prev = a;
            b.next = c;
            c.prev = b;
            c.next = null;
            nodes[0] = a;
            nodes[1] = b;
            nodes[2] = c;
        }
    
        public static void main(String[] args) {
            Node head = nodes[0];
            printNodes(head);
            Node newHead = reverseLinkedList(head);
            System.out.println("\n反转后：");
            printNodes(newHead);
        }
    
        public static void printNodes(Node head) {
            while (head != null) {
                System.out.println(head.prev + " <-- " + head.value + " --> " + head.next);
                head = head.next;
            }
        }
    
        public static class Node {
            public Node prev;
            public int value;
            public Node next;
    
            public Node(int value) {
                this.value = value;
            }
            public String toString() {
                return Integer.valueOf(value).toString();
            }
        }
    
        /**
         * prev <-- head --> next
         */
        public static Node reverseLinkedList(Node head) {
            Node prev = null;
            Node next = null;
            while (head != null) {
                next = head.next;
                prev = head.prev;
                head.prev = next;
                head.next = prev;
                prev = head;
                head = next;
            }
            return prev;
        }
    }

# 二、把给定值的节点都删除 #

LeetCode 地址：[剑指 Offer 18. 删除链表的节点][Offer 18.]

/**
         * 2 -> 2-> 3-> 2-> 3-> 4
         * 若：删除 num = 3，得到：
         * 2 -> 2-> 2-> 4，return head = 2
         * 若：删除 num = 2 得到：
         * 3-> 3-> 4 ，return head= 3
         * @param head
         * @param val
         * @return
         */
        public static ListNode removeValue(ListNode head, int val) {
            // head 来到第一个不需要删除的位置
            while(head != null) {
                if (head.val != val) {
                    break;
                }
                head = head.next;
            }
            // 1、head == null 表示所有 node 都是 num，return null
            // 2、head != null
            ListNode prev = head;
            ListNode curr = head;
            while (curr != null) {
                if (curr.val == val)
                    prev.next = curr.next;
                else
                    prev = curr;
                curr = curr.next;
            }
            return head;
        }

[Offer 18.]: https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof/