循环与链表

/ 数据结构与算法 / 1 条评论 / 2401浏览

循环不变式 -- loop invariant

所谓循环不变式就是

比如:这是一个循环框架

var a,b;
while() {

}

所谓循环不变式就是a,b必须满足的条件,即进入循环前和退出循环后条件仍然满足

循环书写方法

例一:链表反转

如图,将第一条链表反转,结果是第二条

前言

我在上一篇中使用递归反转链表,但如果这个链表有一百万个元素,此时系统的开销就比较大了,解决方法是使用循环。

分析

当我们使用循环处理链表时和递归不同,若从首元入手会遇到很多边界条件,所以切入点为循环进行中的某刻。

推进循环不变式

每次向前推进的规模为1

代码

    public Node reverseLinkedList(Node head) {
        // newHead指向已经逆置的链表
        Node newHead = null;
        // curHead指向当前未逆置的链表
        Node curHead = head;

        while (curHead != null) {
            Node next = curHead.getNext();
            curHead.setNext(newHead);
            newHead = curHead;
            curHead = next;
        }
        return newHead;
    }

测试用例

    public static void main(String[] args) {
        LinkedListReverser reverser = new LinkedListReverser();
        LinkedListCreator creator = new LinkedListCreator();

        Node.printLinkedList(reverser.reverseLinkedList(
                creator.createLinkedList(Arrays.asList(1, 2, 3, 4, 5)))
        );
        Node.printLinkedList(reverser.reverseLinkedList(
                creator.createLinkedList(Arrays.asList(1)))
        );
        Node.printLinkedList(reverser.reverseLinkedList(
                creator.createLinkedList(new ArrayList<Integer>()))
        );
    }

例二:链表中的delete_if

删除这个链表中元素值为2的结点

分析

删除链表中的某个节点,只需将这个节点的前一个节点的next域指向这个节点的后一个节点即可。

推进循环不变式

这里我们增加一个变量 previous 用于指向删除结点的前一个结点

previous 指向需要删除结点的后一个节点即可,也就是跳过需要删除结点

代码

    public Node deleteIfEquals(Node head, int value) {

        while (head != null && head.getValue() == value) {
            head = head.getNext();
        }
        if (head == null) {
            return null;
        }

        Node previous = head;
        while (previous.getNext() != null) {
            if (previous.getNext().getValue() == value) {
                // delete this value
                previous.setNext(previous.getNext().getNext());
            } else {
                previous = previous.getNext();
            }
        }
        return head;
    }

测试用例

    public static void main(String[] args) {
        LinkedListCreator creator = new LinkedListCreator();
        LinkedListDeletor deletor = new LinkedListDeletor();

        Node.printLinkedList(deletor.deleteIfEquals(
                creator.createLinkedList(Arrays.asList(1, 2, 2, 3, 4)), 2)
        );
        Node.printLinkedList(deletor.deleteIfEquals(
                creator.createLinkedList(Arrays.asList(2, 2, 2, 3, 4)), 2)
        );
        Node.printLinkedList(deletor.deleteIfEquals(
                creator.createLinkedList(Arrays.asList(2)), 2)
        );
        Node.printLinkedList(deletor.deleteIfEquals(
                creator.createLinkedList(Arrays.asList(2)), 1)
        );
        Node.printLinkedList(deletor.deleteIfEquals(
                creator.createLinkedList(Arrays.asList(2, 2, 2, 2, 2, 2)), 2)
        );
        Node.printLinkedList(deletor.deleteIfEquals(
                creator.createLinkedList(Arrays.asList(2, 2, 3, 2, 2)), 2)
        );
        Node.printLinkedList(deletor.deleteIfEquals(
                creator.createLinkedList(new ArrayList<Integer>()), 2)
        );
    }

头结点没有previous怎么办

提示:完整代码放在了我的 gitee 上面

  1. 厉害了习铭!