1、移除未排序的链表中的重复结点

暴力破解

  用两个指针来迭代链表:current 指针迭代访问整个链表,runner 指针用于检查后续的结点是否重复。

public static void deleteDups (ListNode<Integer> head) {
        if (head == null) {
            return;
        }
        ListNode<Integer> current = head;
        // 遍历链表
        while (current != null) {
            ListNode<Integer> runner = current;
            while (runner.next != null) {
                // 如果有相同的元素,则删除一个元素
                if (runner.next.data.equals(current.data)) {
                    runner.next = runner.next.next;
                } else {
                    runner = runner.next;
                }
            }
            current = current.next;
        }
    }

使用哈希表

  要想移除链表中的重复结点,我们需要设法记录迭代过的结点,这里使用哈希表记录迭代过的结点。
  在下面的解法中,我们会直接迭代访问整个链表,将每个结点加入到哈希表。若发现有重复的元素,将该结点从链表中移除,然后继续迭代。

    /**
     * 直接迭代访问整个链表,将每个节点加入哈希表。若发现有重复元素,则将该结点从链表中移除,然后继续迭代。
     */
    public static void deleteDups(ListNode<Integer> head) {
        // 创建哈希表
        Set<Integer> set = new HashSet<>();
        ListNode<Integer> pre = null;
        while (head != null) {
            if (set.contains(head.data)) {
                // 如果已存在,则将上一个结点的尾指针指向当前结点的尾指针(删除)
                pre.next = head.next;
            } else {
                set.add(head.data);
                pre = head;
            }
            head = head.next;
        }
    }

2、删除链表中倒数第 k 个结点

解法
  使用两个指针 kPointer 和 head 遍历链表,两个指针间隔数为 k,当 head 指针移动到链表尾部时候,kPointer 指针就指向了倒数第 k 个节点。

    public static ListNode<Integer> reciprocal(ListNode<Integer> head, int k) {
        if (head == null || k <= 0) {
            return null;
        }
        // 两个指针的间隔,倒数第K个和倒数第一个间隔k-1,所以默认值是1
        int count = 1;
        // K 的指针
        ListNode<Integer> kPointer = head;
        // 决定 k 的指针是否需要移动
        boolean flag = false;
        while (head.next != null) {
            // 当间隔数等于k时候,k指针开始移动
            if (count == k) {
                flag = true;
            } else {
                count++;
            }
            if (flag) {
                // 移动k指针
                kPointer = kPointer.next;
            }
            head = head.next;
        }
        // 当 count < k 说明 倒数 k 的值不存在
        if (count < k) {
            return null;
        }
        return kPointer;
    }

3、删除当前结点

  给定带删除的结点,请执行删除操作,若该结点为尾结点,返回 false,否则返回 true。实现一个算法,删除单链表中间的某个结点,假定你不能访问该结点的前驱。

解法
  既然不能访问该结点的前驱,就拷贝下一个结点的数据,然后删除下一个结点。

public boolean removeNode (ListNode<Integer> node){
        if(node.next==null){
            return false;
        }
        // 存储下一个结点的数据
        node.data=node.next.data;
        // 指针指向下下一个结点
        node.next=node.next.next;
        return true;
    }

4、分割链表

  编写代码,以给定值 x 为基准将链表分割成两部分,所有小于 x 的结点排在大于或等于 x 节点之前。给定一个链表的头指针 ListNode * head,请返回重新排列后的链表的头指针。注意:分割以后保持原来的数据顺序不变。
例子
链表:5 6 3 2 1,x:3
输出:2 1 5 6 3

解法
  定义左右两个链表和 pointer 指针,指针指向链表头部开始对链表进行迭代。当值小于 x 时,将结点存储到左链表中;当值大于等于 x 时,将结点存储到右链表中,最后合并链表即可。

    public static ListNode<Integer> partition(ListNode<Integer> head, int x) {
        // 定义左边和右边的头尾
        ListNode<Integer> leftFirst = null;
        ListNode<Integer> leftTail = null;
        ListNode<Integer> rightFirst = null;
        ListNode<Integer> rightTail = null;
        ListNode<Integer> pointer = head;
        // 顺序扫描所有节点
        while (pointer != null) {
            // 当值小于 x时
            if (pointer.data < x) {
                if (leftTail == null) {
                    // 如果是第一次则初始化左边的头和尾
                    leftFirst = pointer;
                    leftTail = pointer;
                } else {
                    // 将p追加到左边的尾部
                    leftTail.next = pointer;
                    // 更新左边尾部的值
                    leftTail = pointer;
                }
            } else {
                // 当值大于等于 x 时
                if (rightTail == null) {
                    // 初始化右边的头和尾
                    rightFirst = pointer;
                    rightTail = pointer;
                } else {
                    rightTail.next = pointer;
                    rightTail = pointer;
                }
            }
            pointer = pointer.next;
        }
        // 左边链表可能为空
        if (leftFirst == null) {
            return rightFirst;
        }
        // 将左右两个链表串起来
        leftTail.next = rightFirst;
        // 如果右边链表不为空,则将右边链表尾部的下一个赋值空(设置结尾)
        if (rightTail != null) {
            rightTail.next = null;
        }
        return leftFirst;
    }

5、链表的加法

  有两个用链表表示的整数,每个节点包含一个数位。这些数位是反向存放的,也就是个位排列在链表的首部。编写函数对这两个整数求和,并用链表形式返回结果。给定两个链表 A,B,请返回 A+B 的结果值。

例子
输入:{1,2,3}{1,2,3,4}
输出:{2,4,6,4}

  当数位是反向存放时,对两个链表从头开始遍历,如果数位和大于 10 则向下一个结点进位即可。

    public static ListNode<Integer> plusAB(ListNode<Integer> a, ListNode<Integer> b) {
	// 头结点进位为0
        return plusAB(a, b, 0);
    }

    /**
     * a和b表示当前位的数,i表示前一位的进的位
     */
    public static ListNode<Integer> plusAB(ListNode<Integer> a, ListNode<Integer> b, int i) {
        // 如果都为空,且i为0表示已经遍历完
        if (a == null & b == null && i == 0) {
            return null;
        }
        int value = i;
        if (a != null) {
            value += a.data;
        }
        if (b != null) {
            value += b.data;
        }
        ListNode<Integer> result = new ListNode<>(value % 10);
        result.next = plusAB(a == null ? null : a.next, b == null ? null : b.next, value >= 10 ? 1 : 0);
        return result;
    }

进阶:假设是正向存放的

例子
输入:{1,2,3}{1,2,3,4}
输出:{1,3,5,7}

  如果数位是正向存放的,且当两个链表的长度不相等时,用 0 对短链接表进行填充,使其长度和长链表相等。然后从尾结点进行相加向前进位即可。

    public static ListNode<Integer> reversePlusAB(ListNode<Integer> a, ListNode<Integer> b) {
        int len1 = length(a);
        int len2 = length(b);
        //用零填充较短的链表
        if (len1 < len2) {
            a = padList(a, len2 - len1);
        } else {
            b = padList(b, len1 - len2);
        }
        //对两个链表求和
        PartialSum sum = addListsHelper(a, b);
        //如有进位,则插入链表首部,否则,直接返回整个链表
        if (sum.carry == 0) {
            return sum.node;
        } else {
            return insertBefore(sum.node, sum.carry);
        }
    }

    public static PartialSum addListsHelper(ListNode<Integer> a, ListNode<Integer> b) {
        // 因为 a,b链表长度相同,一个为空另一个也为空
        if (a == null) {
            return new PartialSum();
        }
        //先递归为较小数字求和
        PartialSum sum = addListsHelper(a.next, b.next);
        //将进位和当前数据相加
        int val = sum.carry + a.data + b.data;
        //插入当前数字的求和结果
        sum.node = insertBefore(sum.node, val % 10);
        //返回求和结果与进位值
        sum.carry = val / 10;
        return sum;
    }

    /**
     * 将结点插入链表首部
     */
    public static ListNode<Integer> insertBefore(ListNode<Integer> list, int data) {
        ListNode<Integer> node = new ListNode<>(data);
        if (list != null) {
            list.pre = node;
            node.next = list;
        }
        return node;
    }

    /**
     * 计算链表的长度
     */
    public static int length(ListNode<Integer> node) {
        int size = 0;
        while (node != null) {
            size++;
            node = node.next;
        }
        return size;
    }

    /**
     * 用零填充链表
     */
    public static ListNode<Integer> padList(ListNode<Integer> node, int padding) {
        ListNode<Integer> head = node;
        for (int i = 0; i < padding; i++) {
            ListNode<Integer> n = new ListNode<>(0);
            head.pre = n;
            n.next = head;
            head = n;
        }
        return head;
    }

    public static class PartialSum {
        /**
         * 当前结点
         */
        public ListNode<Integer> node = null;
        /**
         * 向前进位
         */
        public int carry = 0;
    }

6、判断一个链表是不是环链表

  使用两个速度不一样的指针进行移动,如果两个指针相遇,则表示该链表是一个环。

  /**
     * 判断一个链表是不是环链表
     */
    public static boolean hasCircle(ListNode<Integer> head) {
        ListNode<Integer> s = head;
        ListNode<Integer> f = head;
        while (true) {
            if (f == null || f.next == null) {
                return false;
            }
            // s 指针每次移动一个节点
            s = s.next;
            // f 指针每次移动两个节点
            f = f.next.next;
            if (s == f) {
                return true;
            }
        }
    }

7、求环链表的头结点

  给定一个有环链表,实现一个算法返回环路的开头结点。有环链表的定义:在链表中某个节点的 next 元素指向在它前面出现过的节点,则表明该链表存在环路。

使用哈希表

  如果一个结点出现两次则表明该结点是环链表的头结点。

public static ListNode<Integer> check(ListNode<Integer> head) {
        ListNode<Integer> p = head;
        HashSet<ListNode<Integer>> set = new HashSet<ListNode<Integer>>();
        while (true) {
            if (set.contains(p)) {
                return p;
            } else {
                set.add(p);
                p = p.next;
            }
        }
    }

测试

public static void main(String[] args) {
        ListNode<Integer> listNode=new ListNode<Integer>(1);
        listNode.next=new ListNode<Integer>(2);
        listNode.next.next=new ListNode<Integer>(3);
        listNode.next.next.next=new ListNode<Integer>(4);
        listNode.next.next.next.next=listNode.next;
        System.out.println(check(listNode).data);
    }

使用双指针

  使用两个指针 s 和 f,s 指针每次移动一个结点,f 指针每次移动两个结点。如图:

环.png

代码实现

public static ListNode<Integer> beginOfCircle(ListNode<Integer> head) {
        ListNode<Integer> s = head;
        ListNode<Integer> f = head;
        do {
            // s 指针每次移动一个节点
            s = s.next;
            // f 指针每次移动两个节点
            f = f.next.next;
        } while (s != f);
        // 结束循环时 s 还差 k 个节点就走到了环路的开头节点
        // 而链表的开头节点和环路的开头节点也相差 k 个节点
        ListNode<Integer> p = head;
        // p 指针和 s 指针同时移动,相同点就是环路的开头节点
        while (p != s) {
            p = p.next;
            s = s.next;
        }
        return p;
    }

先判断是否是环链表,再求出头结点

public static ListNode<Integer> beginOfCircle1(ListNode<Integer> head) {
        ListNode<Integer> s = head;
        ListNode<Integer> f = head;
        // 判断链表是不是环链表
        while (f != null && f.next != null) {
            s = s.next;
            f = f.next.next;
            if (s == f) {
                break;
            }
        }
        // 判断循环是以何种方式退出的
        if (f == null || f.next == null) {
            return null;
        }
        ListNode<Integer> p = head;
        while (p != s) {
            p = p.next;
            s = s.next;
        }
        return p;
    }

8、桶排序

  桶排序的原理是将数分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时间,桶排序使用线性时间 O(n),但桶排序并不是比较排序,它不受到 O(nlogn)下限的影响。

  桶排序假设数据会均匀入桶,在这个前提下桶排序速度很快。对于 Java 语言可以不用自己定义链表,直接使用 LinkedList 类。

    /**
     * 时间复杂度 O(N+C),其中 C=N*(logN-logM)
     * 空间复杂度 N+M,M 为桶的个数
     * 稳定性:稳定
     */
    private static void sort(int[] array) {
        int length = array.length;
        // 桶的个数
        LinkedNode[] bucket = new LinkedNode[length];
        // 获取数组中的最大值
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (max < array[i]) {
                max = array[i];
            }
        }
        // 入桶
        for (int value : array) {
            // 桶的下标
            int hash = hash(value, max, length);
            if (bucket[hash] == null) {
                // 初始化链表表头
                bucket[hash] = new LinkedNode(value);
            } else {
                // 插入链表
                insertInto(value, bucket[hash], bucket, hash);
            }
        }
        // 记录数组下标
        int k = 0;
        for (LinkedNode node : bucket) {
            if (node != null) {
                while (node != null) {
                    array[k++] = node.value;
                    node = node.next;
                }
            }
        }
    }

    /**
     * 根据桶的个数来确定hash函数,这份代码适合桶的个数等于数组长度
     */
    private static int hash(int element, int max, int length) {
        return (element * length) / (max + 1);
    }

    private static void insertInto(int value, LinkedNode head, LinkedNode[] bucket, int hash) {
        LinkedNode newNode = new LinkedNode(value);
        // 小于头节点,放在头上
        if (value <= head.value) {
            newNode.next = head;
            // 替换头节点
            bucket[hash] = newNode;
            return;
        }
        // 往后找第一个比当前值大的节点,放在这个节点的前面
        LinkedNode p = head;
        LinkedNode pre = p;
        while (p != null && value > p.value) {
            pre = p;
            p = p.next;
        }
        // 跑到末尾
        if (p == null) {
            pre.next = newNode;
        } else {
            // 插入pre和p之间
            pre.next = newNode;
            newNode.next = p;
        }
    }

标题:链表经典练习题
作者:Yi-Xing
地址:http://zyxwmj.top/articles/2020/03/03/1583246683883.html
版权声明:本文为博主原创文章,转载请附上博文链接!
博客中若有不恰当的地方,请您一定要告诉我。前路崎岖,望我们可以互相帮助,并肩前行!

添加新评论