算法分析 2019-02-13

向后链表的通用解决

1. 使用prev做前驱记忆解决头节点删除无法遍历问题
2. 使用slow + fast两个可以快速向后跳跃
3. 使用cur 记录当前节点所在位置

1. 删除链表中重复的值

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

1.1 数据有序，保留一个 easy

获取头结点为cur, 每次判断下一节点值是否等于cur，如果相等cur.next设置为cur.next.next

  public ListNode deleteDuplicates(ListNode head) {
        ListNode cur = head;
        while(cur != null && cur.next != null) {
            int x = cur.val;
            int n = cur.next.val;
            if(x == n) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;
    }

1.2 数据有序，所有值 medium

设置头指针h 和 前缀节点pre来进行删除滑动窗口指针删除

public ListNode deleteDuplicates(ListNode head) {
        // 保证有2个值
        if(head == null || head.next == null) return head;
        ListNode h = new ListNode(-1);
        h.next = head;
        ListNode pre = h;
        ListNode slow = h.next;
        ListNode fast = slow.next;
        while(slow != null && fast != null) {
            if(slow.val == fast.val) {
            // 这里做窗口, 进行移动
                while(fast != null && slow.val == fast.val) {
                    fast = fast.next;
                }
                pre.next = fast;
                slow = fast;
                fast = fast == null ? null : fast.next;
            } else {
                pre = slow;
                slow = slow.next;
                fast = fast.next;
            }
        }
        return h.next;
    }

更好的方案, 利用地址唯一的特性来判断是否存在重复的值，这样少一次滑动判断

    public ListNode deleteDuplicates(ListNode head) {
        // 保证有1个值
        if(head == null) return head;
        // 设置头指针 和 前缀指针
        ListNode h = new ListNode(-1);
        h.next = head;
        ListNode pre = h;
        ListNode cur = head;
        while(cur != null) {
            while(cur.next != null && cur.val == cur.next.val) {
                cur = cur.next;
            }
            if(pre.next == cur) {
                pre = pre.next;
            } else {
                pre.next = cur.next;
            }
            cur = cur.next;
        }
        return h.next;
    }

2. 求中位数的后续列表 有序 easy

使用 slow 和 fast 快慢引用, 中位数的特性就是fast是slow的两倍

public ListNode middleNode(ListNode head) {
        int size = 0;
        ListNode slow = head, fast = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

3. 删除链表中指定的值 easy

使用分治法，先把最后的节点判断是否删除，如果需要使用其后一个节点连接，否则使用当前节点连接，依次向前类推

public ListNode removeElements(ListNode head, int val) {
        if(head == null) return null;
        head.next = removeElements(head.next, val);
        return head.val == val ? head.next : head;
    }