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

拼搏现实的明天。 2022-01-10 08:07 322阅读 0赞

[关于链表的常见算法题(一)][Link 1]

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

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

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

Input: 1->1->2->3->3
    Output: 1->2->3
    复制代码

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

##### 解题思路 #####

*  遍历链表，如果当前节点与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][CSDN]

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

转载于:https://juejin.im/post/5d07aed85188252354279693

[Link 1]: https://juejin.im/post/5d067f4ee51d4577596486fb
[juejin.im_post_5d067f]: https://juejin.im/post/5d067f4ee51d4577596486fb#heading-5
[CSDN]: https://link.juejin.im?target=https%3A%2F%2Fblog.csdn.net%2FApkCore