1472. Design Browser History #

题目 #

现有一个只支持单个标签页的 浏览器，最开始浏览的网页是 homepage，可以访问其他的网站 url，也可以在浏览器中后退 steps 步或前进 steps 步。

设计实现 BrowserHistory 类：

BrowserHistory(string homepage) 用 homepage 初始化浏览器类。
void visit(string url) 从当前页面跳转访问 url 对应的页面。执行此操作会把浏览历史前进的记录全部删除。
string back(int steps) 在浏览历史中后退 steps 步。如果只能在浏览历史中后退至多 x 步且 steps > x，那么只后退 x 步。请返回后退至多 steps 步以后的 url。
string forward(int steps) 在浏览历史中前进 steps 步。如果只能在浏览历史中前进至多 x 步且 steps > x，那么只前进 x 步。请返回前进至多 steps 步以后的 url。

思路 #

借助双向链表实现。
注意 visit 操作执行后会将浏览历史前进的记录全部删除。

代码 #

class BrowserHistory {
    private class ListNode {
        public String url;
        public ListNode prev;
        public ListNode next;
        ListNode(String url, ListNode prev, ListNode next) {
            this.url = url;
            this.prev = prev;
            this.next = next;
        }
    }
    
    private ListNode head;
    private ListNode ptr;
    
    public BrowserHistory(String homepage) {
        this.head = new ListNode(homepage, null, null);
        this.head.next = this.head.prev = this.head;
        this.ptr = head;
    }
    
    public void visit(String url) {
        this.ptr.next = new ListNode(url, this.ptr, this.head);
        this.head.prev = this.ptr.next;
        this.ptr = this.ptr.next;
    }
    
    public String back(int steps) {
        for (int i=0; i<steps; i++) {
            if (this.ptr == this.head) return this.ptr.url;
            else this.ptr = this.ptr.prev;
        }
        return this.ptr.url;
    }
    
    public String forward(int steps) {
        for (int i=0; i<steps; i++) {
            if (this.ptr.next == this.head) return this.ptr.url;
            else this.ptr = this.ptr.next;
        }
        return this.ptr.url;
    }
}