关于链表的常见算法题(二)

1,453 阅读8分钟

关于链表的常见算法题(一)

关于链表的常见算法题(二)

从有序链表中删除重复的节点

给定一个有序链表,请删除其中的重复元素,使得这个元素仅出现一次

Input: 1->1->2->3->3
Output: 1->2->3

其实这个题比上篇讲的juejin.cn/post/684490…中删除重复的节点还要容易一些,因为在此处,有重复的值时,是保留一个节点的,而上一篇中是都删除。

解题思路
  • 遍历链表,如果当前节点与next的下一个节点相同,那么删除下一个节点,并把指针next指向next.next。这里很明显我们可以使用递归来解决问题
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        head.next = deleteDuplicates(head.next);
        return head.value == head.next.value ? head.next : head;
    }

删除重复元素

给定一个有序链表,请删除其中的重复元素,使得原链表中的元素只出现一次

Input: 2->3->4->2->null
Output: 2->3->4->null
解题思路

可以使用双循环暴力破解法,不过时间复杂度就是O(n^2)了,我们可以使用HashMap和存储结点值,判断是否有重复,有重复的时候,把当前节点的上一个节点的next指向当前节点的next,这样,就相当于把当前节点删除了,当没有重复时,把这个值加入map中。

    /**
     * 双循环
     */
    public ListNode deleteDulp(ListNode head) {
        if (head==null||head.next==null){
            return head;
        }
        ListNode p = head;
        while (p != null) {
            ListNode q= p;
            while (q.next!=null){
                if (p.value==q.next.value){
                    q.next  = q.next.next;
                }else {
                    q = q.next;
                }
            }
            p = p.next;
        }
        return head;
    }

    /**
     * 使用hashmap
     */
    public ListNode deleteDulp2(ListNode head){
        HashMap<Integer,Integer>  map = new HashMap<>();
        ListNode root = head;
        ListNode before = head;
        while (head!=null){
            if (map.containsKey(head.value)) {
                before.next =  head.next;
                head = head.next;
            }else {
                map.put(head.value,1);
                before = head;
                head = head.next;
            }
        }
        return root;
    }

删除链表的倒数第n个节点

给定一个单向链表,要求删除从结尾数第n个结点,并返回链表

输入:5-6-7-8-9  n=2;
输出:5-6-7-9
解题思路

核心是找到要删除的结点的前一个结点位置。我们可以使用双指针来完成,快指针先走n-1步,然后同时移动快慢双指针,当快指针的的next为null时,我们就找到了当前位置就我们要找的位置

    public ListNode removeNthFormEnd(ListNode head, int n) {
        ListNode fast = head;
        while (n-- > 0) {
            fast = fast.next;
        }
        if (fast == null) {
            return head.next;
        }
        ListNode slow = head;
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return head;
    }

交换链表中的相邻结点

给定一个单向链表,依次交换每一对相邻的结点

1-2-3-4
2-1-4-3
解题思路

首先我们要明白,链表的两个结点要如何交换:

假如有1-2-3-4-5这个链表,我们要交换的是3和4,那么

  • 先把3的上一外结点的指向4,得到链表A 1-2-4-5,另外一种形式是3-4-5
  • 再把3指下4的next,得到3-5
  • 然后整合两条链,将4指向3,得到1-2-4-3-5

我们想到头插法反转,指定一个pre指针,指向头插的节点,反转后两个节点,pre指针指向以前的next,比如增加头结点0,那么0-1-2-3-4,先把pre指向0,此时pre.next为1,把1和2反转后,变成0-2-1-3-4,再把pre指针移到1的位置,后面一样的循环就好了。

    public ListNode swapPairs(ListNode head) {
        //在头部增加一个节点
        ListNode node = new ListNode(-1);

        node.next = head;
        ListNode pre = node;
        while (pre.next != null && pre.next.next != null) {
            ListNode node1 = pre.next;
            ListNode node2 = pre.next.next;

            node1.next = node2.next;
            node2.next = node1;
            pre.next = node2;

            //此时node1已经反转,这个位置就是我们要的位置
            pre = node1;
        }

        return node.next;
    }

反转k个相邻的结点

给定一个单向链表,每次反转k个相邻结点,返回最终修改后的链表。k是一个正整数,并且不大于链表长度。如果链表中的节点个数不是k的整数倍,则最后剩余的k个结点不做修改

输入:1-2-3-4-5  k=2
输出:2-1-4-3-5
解题思路

这题其实是上一个题的升级版,所以我们依然可以套用上一个题目的方法

  • 使用头插法

    建立另外一个链表头,然后要处理的列表递进处理,一个个的插入新链表,最后返回这的next。

    核心思想是两个两个操作,操作k-1次。操作的内容是用prev与next节点指向新头节点,然后操作指针关系。

  • 使用递归法

    设置好分组的间隔,用cnt和curNode分别标识计数和目前的节点,当分组结束后开始递归下一组分组,并开始这一组的反转操作,仍然用cnt和curNode控制组内收缩。

    /**
     * 使用头插法
     */
    public ListNode reverseKGroup2(ListNode head, int k) {
        if (head == null || head.next == null || k == 1) {
            return head;
        }

        //找到链表的长度n
        int n = 0;
        ListNode root = head;
        while (root != null) {
            root = root.next;
            n++;
        }

        //使用头插
        ListNode node = new ListNode(-1);
        node.next = head;
        for (ListNode prev = node, tail = head; n >= k; n -= k) {
            for (int i = 1; i < k; i++) {
                ListNode next = tail.next.next;
                tail.next.next = prev.next;
                prev.next = tail.next;
                tail.next = next;
            }

            prev = tail;
            tail = tail.next;
        }
        return node.next;

    }

    /**
     * 使用递归法
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode curNode = head;
        int cnt = 0;
        //把cnt都移动到k位,curNode移动到下一次反转开始的地方
        while (curNode != null && cnt != k) {
            curNode = curNode.next;
            cnt++;
        }
        if (cnt == k) {
            curNode = reverseKGroup(curNode, k);
            while (cnt-- > 0) {
                ListNode temp = head.next;
                head.next = curNode;
                curNode = head;
                head = temp;
            }
            head = curNode;
        }

        return head;
    }

链表求和

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7
解题思路

我们可以发现,其实就是倒序对应相加,有进位的话要保存到下次相加上,想到了栈这样的数据结构,后进先出

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> l1Stack = buildStack(l1);
        Stack<Integer> l2Stack = buildStack(l2);
        ListNode head = new ListNode(-1);
        int carry = 0;
        while (!l1Stack.isEmpty() || !l2Stack.isEmpty() || carry != 0) {
            int x = l1Stack.isEmpty() ? 0 : l1Stack.pop();
            int y = l2Stack.isEmpty() ? 0 : l2Stack.pop();
            int sum = x + y + carry;
            ListNode node = new ListNode(sum % 10);
            //头插法
            node.next = head.next;
            head.next = node;
            carry = sum / 10;
        }
        return head.next;
    }

    private Stack<Integer> buildStack(ListNode listNode) {
        Stack<Integer> stack = new Stack<>();
        while (listNode != null) {
            stack.push(listNode.value);
            listNode = listNode.next;
        }
        return stack;
    }

回文链表

给定一个单链表,判断它是否是回文链表,即正着遍历和反着遍历得到的序列是相同的。

要求,0(1)空间复杂度

解题思路

因为要求的空间复杂度为O(1),所以栈啊什么的数据结构来存储的就不能用了,这时候需要用到分治的思想

我们可以把链切成两半,把后半段反转,再比较这两半是否相等就可以了。

具体可以这么来实现,使用快慢两个指针,快指针每次两步,慢指针每次一步,当快指针的next或者next.next为空时,慢指针就在链表的中间(偶数个时,慢指针是靠近头那一侧的节点)。然后从慢指针的下一个点开始把后面的链表反转,然后分别从头和尾(这个时候尾已经转到了中间)前进,这可以判断是否是一个回文

    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        ListNode fast = head;
        ListNode slow = head;
        //找到中点
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        //后面一段的开始点
        ListNode secondHead = slow.next;
        ListNode p1 = secondHead;
        ListNode p2 = p1.next;

        slow.next = null;//把原来的置空
        while (p1 != null && p2 != null) {
            ListNode temp = p2.next;
            p2.next = p1;
            p1 = p2;
            p2 = temp;
        }

        //将第二段链表的尾巴置空,已经转过来了,头就是尾
        secondHead.next = null;

        while (p1 != null) {
            if (head.value != p1.value) {
                return false;
            }
            head = head.next;
            p1 = p1.next;
        }
        return true;
    }

分隔链表

给定一个头结点为 root 的链表, 编写一个函数以将链表分隔为 k 个连续的部分。

每部分的长度应该尽可能的相等: 任意两部分的长度差距不能超过 1,也就是说可能有些部分为 null。

这k个部分应该按照在链表中出现的顺序进行输出,并且排在前面的部分的长度应该大于或等于后面的长度。

返回一个符合上述规则的链表的列表。

输入: root = [1, 2, 3], k = 5
输出: [[1],[2],[3],[],[]]
解题思路

计算出链表的长度,然后根据n/k求出数组长度,n%k不为0时说明不能均分,所以从第一个开始,链表长度加1,mod--,直到0

    public ListNode[] splitListToParts(ListNode root, int k) {
        int n = 0;
        ListNode cur = root;
        
        //计算链表长度
        while (cur != null) {
            n++;
            cur = cur.next;
        }
        
        int mod = n % k;
        int size = n / k;
        ListNode[] ret = new ListNode[k];
        //重新把root赋值给cur
        cur = root;
        for (int i = 0; cur != null && i < k; i++) {
            ret[i] = cur;
            int curSize = size + (mod-- > 0 ? 1 : 0);
            for (int j = 0; j < curSize - 1; j++) {
                cur = cur.next;
            }
            ListNode next = cur.next;
            cur.next = null;
            cur = next;
        }
        return ret;
    }

链表元素按奇偶聚集

给定一个单链表,请将所有的偶数节点拿出来,放在奇数节点后面,注意,偶数指的是节点的位置编号,而不是值。

你需要使用O(N)的时间和O(N)的空间

解题思路

这个还是可以通过双指针来解决,用两个指针一起遍历,每次遍历两个节点,然后再将偶数链表头接在奇数尾上。

    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode odd = head;//放奇数
        ListNode even = head.next;//放偶数
        ListNode evenHead = even;
        while (even != null && even.next != null) {
            //先把odd的next指向下一个奇数,然后把odd的指针切换到这个奇数上
            odd.next = odd.next.next;
            odd = odd.next;
            even.next = even.next.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }

By LeetCode


我的CSDN

下面是我的公众号,欢迎大家关注我