链表之5个常见的链表操作

末蓝、 2021-09-18 04:28 243阅读 0赞

一定要画图！！！

1.  单链表翻转

public class ListNodeReverse {
    
        public static void reverse(ListNode<String> node) {
            if (node == null || node.next == null)
                return;
    
            ListNode<String> pre = null;
            while (node != null) { // 注意这个条件是 node != null, 如果是 node.next != null,
                                   // 会丢到最后一个指针
                // 保存指针，防止断链
                ListNode<String> cur = node.next;
                node.next = pre;
                pre = node;
                // 继续遍历
                node = cur;
            }
        }
    
        public static void main(String[] args) {
            ListNode<String> node5 = new ListNode<>(null, "a");
            ListNode<String> node4 = new ListNode<>(node5, "b");
            ListNode<String> node3 = new ListNode<>(node4, "c");
            ListNode<String> node2 = new ListNode<>(node3, "d");
            ListNode<String> node1 = new ListNode<>(node2, "e");
            ListNode<String> head = node1;
            while (head != null) {
                System.out.println(head.toString());
                head = head.next;
            }
            reverse(node1);
            while (node5 != null) {
                System.out.println(node5.toString());
                node5 = node5.next;
            }
        }
    }

1.  链表中环的检测
2.  两个有序的链表合并

public class ListNodeMerge {
    
        public static ListNode<Integer> merge(ListNode<Integer> node1, ListNode<Integer> node2) {
            ListNode<Integer> node = null;
            ListNode<Integer> pre = null;
            if (node1 == null)
                return node2;
            if (node2 == null)
                return node1;
            while (node1 != null && node2 != null) {
                if (node1.value >= node2.value) {
                    if (node == null) {
                        node = node2;
                        pre = node;
                    } else {
                        pre.next = node2;
                        pre = pre.next;
                    }
                    node2 = node2.next;
                } else {
                    if (node == null) {
                        node = node1;
                        pre = node;
                    } else {
                        pre.next = node1;
                        pre = pre.next;
                    }
                    node1 = node1.next;
                }
            }
            if (node2 == null) {
                pre.next = node1;
            }
            if (node1 == null) {
                pre.next = node2;
            }
            return node;
        }
    
        public static void main(String[] args) {
            ListNode<Integer> node5 = new ListNode<>(null, 12);
            ListNode<Integer> node4 = new ListNode<>(node5, 9);
            ListNode<Integer> node3 = new ListNode<>(node4, 6);
            ListNode<Integer> node2 = new ListNode<>(node3, 5);
            ListNode<Integer> node1 = new ListNode<>(node2, 2);
    
            ListNode<Integer> nodev5 = new ListNode<>(null, 13);
            ListNode<Integer> nodev4 = new ListNode<>(nodev5, 10);
            ListNode<Integer> nodev3 = new ListNode<>(nodev4, 8);
            ListNode<Integer> nodev2 = new ListNode<>(nodev3, 4);
            ListNode<Integer> nodev1 = new ListNode<>(nodev2, 1);
    
            ListNode<Integer> node = merge(node1, nodev1);
    
            System.out.println(node);
        }
    }

1.  删除链表倒数第n个节点
2.  求链表的中间节点

public class ListNodeFindMid {
    
        public static ListNode<String> findMid(ListNode<String> head) {
            if (head == null || head.next == null) {
                return head;
            }
            ListNode<String> slow = head;
            ListNode<String> fast = head;
            while (fast.next != null) { // 注意终止条件
                slow = slow.next;
                fast = fast.next.next;
            }
            return slow;
        }
    
        public static void main(String[] args) {
    
            ListNode<String> node5 = new ListNode<>(null, "a");
            ListNode<String> node4 = new ListNode<>(node5, "b");
            ListNode<String> node3 = new ListNode<>(node4, "c");
            ListNode<String> node2 = new ListNode<>(node3, "d");
            ListNode<String> node1 = new ListNode<>(node2, "e");
            ListNode<String> node0 = new ListNode<>(node1, "f");
            ListNode<String> node = new ListNode<>(node0, "g");
    
            System.out.println(findMid(node));
        }
    }