devbox
我家小花儿
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构与算法-链表练习题_int middle = (start +end )/2 ;if(start>=end)

作者：我家小花儿 | 2024-05-07 02:37:58

赞

踩

int middle = (start +end )/2 ;if(start>=end)

leetcode的几道链表练习题：

  1. package com.freshbin.basics.linkedlist;
  2.  
  3. /**
  4.  * @author freshbin
  5.  * @date 2020/5/2 14:54
  6.  */
  7. public class ListNode {
  8.     int val;
  9.     ListNode next;
  10.  
  11.     ListNode(int x) {
  12.         val = x;
  13.     }
  14. }
  1. package com.freshbin.basics.linkedlist;
  2.  
  3. import java.util.PriorityQueue;
  4.  
  5. /**
  6.  * 23. 合并K个排序链表
  7.  *
  8.  * 合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
  9.  * 示例:
  10.  * 输入:
  11.  * [
  12.  *   1->4->5,
  13.  *   1->3->4,
  14.  *   2->6
  15.  * ]
  16.  * 输出: 1->1->2->3->4->4->5->6
  17.  *
  18.  * @author freshbin
  19.  * @date 2020/5/3 14:37
  20.  */
  21. public class Solution23 {
  22.     /**
  23.      * 思路：把k个链表的值都放入新数组，对新数组用归并排序或者快速排序，再把新数组的值存入链表
  24.      *
  25.      * @param lists
  26.      * @return
  27.      */
  28.     public ListNode mergeKLists(ListNode[] lists) {
  29.         if(lists == null || lists.length == 0) {
  30.             return null;
  31.         }
  32.  
  33.         // 获取总的数据量
  34.         int numberSum = 0;
  35.         for(ListNode listNode : lists) {
  36.             while(listNode != null) {
  37.                 listNode = listNode.next;
  38.                 numberSum++;
  39.             }
  40.         }
  41.         // new一个数组存入所有数据
  42.         int[] newArray = new int[numberSum];
  43.         int index = 0;
  44.         for(ListNode listNode : lists) {
  45.             while(listNode != null) {
  46.                 newArray[index++] = listNode.val;
  47.                 listNode = listNode.next;
  48.             }
  49.         }
  50.  
  51.         // 对数组排序
  52.         // 归并排序
  53. //        mergeSort(newArray, 0, numberSum-1);
  54.         // 快速排序
  55.         quickSort(newArray, 0, numberSum-1);
  56.  
  57.         // 将排序后的数组放入链表
  58.         ListNode newNode = new ListNode(-1);
  59.         ListNode currentNode = newNode;
  60.         for(int val : newArray) {
  61.             currentNode.next = new ListNode(val);
  62.             currentNode = currentNode.next;
  63.         }
  64.  
  65.         return newNode.next;
  66.     }
  67.  
  68.     private void quickSort(int[] newArray, int start, int end) {
  69.         if(start >= end) {
  70.             return;
  71.         }
  72.  
  73.         int targetIndex = partition(newArray, start, end);
  74.         quickSort(newArray, start, targetIndex-1);
  75.         quickSort(newArray, targetIndex+1, end);
  76.     }
  77.  
  78.     private int partition(int[] newArray, int left, int right) {
  79.         int targetVal = newArray[right];
  80.         while(left < right) {
  81.             while(newArray[left] <= targetVal && left < right) {
  82.                 left++;
  83.             }
  84.             newArray[right] = newArray[left];
  85.             newArray[left] = targetVal;
  86.             while(newArray[right] >= targetVal && right > left) {
  87.                 right--;
  88.             }
  89.             newArray[left] = newArray[right];
  90.             newArray[right] = targetVal;
  91.         }
  92.  
  93.         return left;
  94.     }
  95.  
  96.     private void mergeSort(int[] newArray, int start, int end) {
  97.         if(start >= end) {
  98.             return;
  99.         }
  100.  
  101.         int middle = (start + end) / 2;
  102.         mergeSort(newArray, start, middle);
  103.         mergeSort(newArray, middle+1, end);
  104.         mergeArray(newArray, start, middle, end);
  105.     }
  106.  
  107.     /**
  108.      * 合并左右两个数组
  109.      * @param newArray
  110.      * @param start
  111.      * @param middle
  112.      * @param end
  113.      */
  114.     private void mergeArray(int[] newArray, int start, int middle, int end) {
  115.         int left = start, right = middle + 1, k = 0;
  116.         int[] tempArr = new int[end-start+1];
  117.         while(left <= middle && right <= end) {
  118.             if(newArray[left] <= newArray[right]) {
  119.                 tempArr[k++] = newArray[left++];
  120.             } else {
  121.                 tempArr[k++] = newArray[right++];
  122.             }
  123.         }
  124.  
  125.         while(left <= middle) {
  126.             tempArr[k++] = newArray[left++];
  127.         }
  128.  
  129.         while(right <= end) {
  130.             tempArr[k++] = newArray[right++];
  131.         }
  132.  
  133.         int index = 0;
  134.         for(int i = start; i <= end; i++) {
  135.             newArray[i] = tempArr[index++];
  136.         }
  137.     }
  138.  
  139.     /**
  140.      * 将k个链表头放入小跟堆中，然后再从中把堆顶元素依次取出来，每取一次，都把当前链表的下一个节点放入堆中
  141.      * 测试发现，放堆中的运行时间还真不如 直接把链表数据都放到数组，再对数组排序后扔回链表，
  142.      * @param lists
  143.      * @return
  144.      */
  145.     public ListNode mergeKListsByHeap(ListNode[] lists) {
  146.         if(lists == null || lists.length == 0) {
  147.             return null;
  148.         }
  149.         // 将k个链表的表头放入优先级队列，即小根堆
  150.         PriorityQueue<ListNode> queue = new PriorityQueue<>((l1, l2) -> l1.val - l2.val);
  151.         for(ListNode listNode : lists) {
  152.             if(listNode != null) {
  153.                 queue.add(listNode);
  154.             }
  155.         }
  156.  
  157.         ListNode head = new ListNode(-1);
  158.         ListNode currentNode = head;
  159.         // 依次取出队列元素，即取出堆顶元素
  160.         while(!queue.isEmpty()) {
  161.             currentNode.next = queue.poll();
  162.             currentNode = currentNode.next;
  163.             if(currentNode.next != null) {
  164.                 // 将该链表的下一节点放入队列，即放入堆中
  165.                 queue.add(currentNode.next);
  166.             }
  167.         }
  168.  
  169.         return head.next;
  170.     }
  171.  
  172. }
  1. package com.freshbin.basics.linkedlist;
  2.  
  3. import java.util.HashSet;
  4.  
  5. /**
  6.  * 141. 环形链表
  7.  * 给定一个链表，判断链表中是否有环。
  8.  * 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
  9.  * 如果 pos 是 -1，则在该链表中没有环。
  10.  * 示例 1：
  11.  * 输入：head = [3,2,0,-4], pos = 1
  12.  * 输出：true
  13.  * 解释：链表中有一个环，其尾部连接到第二个节点。
  14.  *
  15.  * @author freshbin
  16.  * @date 2020/5/3 14:37
  17.  */
  18. public class Solution141 {
  19.  
  20.     /**
  21.      * 思路：遍历链表，用散列表保存遍历过的值
  22.      * 当链表值与散列表值一致，说明出现环，退出
  23.      *
  24.      * @param head
  25.      * @return
  26.      */
  27.     public boolean hasCycle(ListNode head) {
  28.         HashSet hashSet = new HashSet();
  29.         while(head != null) {
  30.             if(hashSet.contains(head)) {
  31.                 return true;
  32.             }
  33.             hashSet.add(head);
  34.             head = head.next;
  35.         }
  36.  
  37.         return false;
  38.     }
  39.  
  40.     /**
  41.      * 快慢指针法，当快指针与慢指针相等，说明有环
  42.      * @param head
  43.      * @return
  44.      */
  45.     public boolean hasCycle01(ListNode head) {
  46.         if(head == null) {
  47.             return false;
  48.         }
  49.  
  50.         ListNode slowNode = head;
  51.         ListNode fastNode = head.next;
  52.         if(slowNode == fastNode) {
  53.             return true;
  54.         }
  55.         while(fastNode != null && fastNode.next != null) {
  56.             if(slowNode == fastNode) {
  57.                 return true;
  58.             }
  59.             slowNode = slowNode.next;
  60.             fastNode = fastNode.next.next;
  61.         }
  62.  
  63.         return false;
  64.     }
  65. }
  1. package com.freshbin.basics.linkedlist;
  2.  
  3. /**
  4.  * 876. 链表的中间结点
  5.  *
  6.  * 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
  7.  * 如果有两个中间结点，则返回第二个中间结点。
  8.  *
  9.  * @author freshbin
  10.  * @date 2020/5/3 14:21
  11.  */
  12. public class Solution876 {
  13.     /**
  14.      * 思路：用两个指针遍历链表，快指针每次都两步，慢指针每次走一步，
  15.      * 如果快指针下一节点或者下下一节点为空，那么就说明快指针走到尽头了
  16.      * 这时候慢指针的下一指针就是中间节点
  17.      *
  18.      * @param head
  19.      * @return
  20.      */
  21.     public ListNode middleNode(ListNode head) {
  22.         if(head == null || head.next == null) {
  23.             return head;
  24.         }
  25.         if(head.next.next == null) {
  26.             return head.next;
  27.         }
  28.         ListNode slowNode = head;
  29.         ListNode fastNode = head.next;
  30.  
  31.         while(fastNode.next != null && fastNode.next.next != null) {
  32.             fastNode = fastNode.next.next;
  33.             slowNode = slowNode.next;
  34.         }
  35.  
  36.         // 慢指针的下一节点就是中间节点
  37.         return slowNode.next;
  38.     }
  39.  
  40.     public static void main(String[] arg) {
  41.         ListNode listNode = new ListNode(1);
  42.         listNode.next = new ListNode(2);
  43.         listNode.next.next = new ListNode(3);
  44.         listNode.next.next.next = new ListNode(4);
  45.  
  46.         Solution876 solution876 = new Solution876();
  47.         System.out.println(solution876.middleNode(listNode).val);
  48.     }
  49. }
  1. package com.freshbin.basics.linkedlist;
  2.  
  3. /**
  4.  * 面试题 02.03. 删除中间节点
  5.  *
  6.  * 实现一种算法，删除单向链表中间的某个节点（除了第一个和最后一个节点，不一定是中间节点），假定你只能访问该节点。
  7.  *
  8.  * 示例：
  9.  * 输入：单向链表a->b->c->d->e->f中的节点c
  10.  * 结果：不返回任何数据，但该链表变为a->b->d->e->f
  11.  *
  12.  * @author freshbin
  13.  * @date 2020/5/3 11:16
  14.  */
  15. public class Solution1462 {
  16.     /**
  17.      * 思路：用两个指针遍历链表，快指针每次都两步，慢指针每次走一步，
  18.      * 如果快指针下一节点或者下下一节点为空，那么就说明快指针走到尽头了
  19.      * 这时候慢指针的下一指针中间节点
  20.      *
  21.      * 提交之后发现，神他妈删除中间节点，这踏马入参原来是要删除的节点，
  22.      * 那踏马这不是删除当前节点吗？
  23.      *
  24.      * 将后面节点的值赋到当前节点，然后把当前节点指针指向后节点的下一节点即可
  25.      *
  26.      * @param node
  27.      */
  28.     public void deleteNode(ListNode node) {
  29.         /*if(node == null || node.next == null || node.next.next == null) {
  30.             return;
  31.         }
  33.         ListNode slowNode = node;
  34.         ListNode fastNode = node.next;
  36.         while(fastNode.next != null && fastNode.next.next != null) {
  37.             slowNode = slowNode.next;
  38.             fastNode = fastNode.next.next;
  39.         }
  41.         // 删除中间节点
  42.         slowNode.next = slowNode.next.next;*/
  43.  
  44.         node.val = node.next.val;
  45.         node.next = node.next.next;
  46.     }
  47.  
  48.     public static void main(String[] arg) {
  49.         ListNode listNode = new ListNode(1);
  50.         listNode.next = new ListNode(2);
  51.         listNode.next.next = new ListNode(3);
  52.         listNode.next.next.next = new ListNode(4);
  53.  
  54.         Solution1462 solution1462 = new Solution1462();
  55.         solution1462.deleteNode(listNode.next.next);
  56.  
  57.         while(listNode != null) {
  58.             System.out.print(listNode.val + "->");
  59.             listNode = listNode.next;
  60.         }
  61.     }
  62. }
  1. package com.freshbin.basics.linkedlist;
  2.  
  3. /**
  4.  * 面试题18. 删除链表的节点
  5.  * 给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
  6.  * 返回删除后的链表的头节点。
  7.  *
  8.  * 示例 1:
  9.  * 输入: head = [4,5,1,9], val = 5
  10.  * 输出: [4,1,9]
  11.  * 解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
  12.  *
  13.  * 示例 2:
  14.  * 输入: head = [4,5,1,9], val = 1
  15.  * 输出: [4,5,9]
  16.  * 解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
  17.  *
  18.  * @author freshbin
  19.  * @date 2020/5/2 15:43
  20.  */
  21. public class Solution1568 {
  22.     /**
  23.      * 思路：遍历链表，如果当前节点的下一节点值与目标值一致，那么将当前节点的指针指向该节点的下下一节点
  24.      * @param head
  25.      * @param val
  26.      * @return
  27.      */
  28.     public ListNode deleteNode(ListNode head, int val) {
  29.         ListNode currentNode = head;
  30.         if(currentNode == null) {
  31.             return null;
  32.         }
  33.         if(currentNode.val == val) {
  34.             return currentNode.next;
  35.         }
  36.         while(currentNode.next != null) {
  37.             if(currentNode.next.val == val) {
  38.                 currentNode.next = currentNode.next.next;
  39.             }
  40.             currentNode = currentNode.next;
  41.         }
  42.         return head;
  43.     }
  44. }
  1. package com.freshbin.basics.linkedlist;
  2.  
  3. /**
  4.  * 面试题24. 反转链表
  5.  *
  6.  * 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
  7.  *
  8.  * 示例:
  9.  * 输入: 1->2->3->4->5->NULL
  10.  * 输出: 5->4->3->2->1->NULL
  11.  *
  12.  * @author freshbin
  13.  * @date 2020/5/2 14:53
  14.  */
  15. public class Solution1573 {
  16.     /**
  17.      * 思路：遍历链表，用一个辅助链表将当前链表对象放入辅助链表
  18.      * 辅助链表当前对象的next指针指向上一个对象, 同时将链表与辅助链表指针都一直往后移动
  19.      *
  20.      * @param head
  21.      * @return
  22.      */
  23.     public ListNode reverseList(ListNode head) {
  24.         if(head == null) {
  25.             return null;
  26.         }
  27.         ListNode listNode = new ListNode(head.val);
  28.         ListNode currentNode = head.next;
  29.         while(currentNode != null) {
  30.             ListNode next = currentNode.next;
  31.             ListNode preNode = listNode;
  32.             currentNode.next = preNode;
  33.             listNode = currentNode;
  34.             currentNode = next;
  35.         }
  36.         return listNode;
  37.     }
  38.  
  39.     public static void main(String[] arg) {
  40.         Solution1573 solution1573 = new Solution1573();
  41.         ListNode listNode = new ListNode(1);
  42.         listNode.next = new ListNode(2);
  43.         listNode.next.next = new ListNode(3);
  44.         solution1573.reverseList(listNode);
  45.     }
  46. }

断断续续写了两三天，复习了快排和归并排序，没想到学过又忘记了。

快排：1、快排是先分成左右两个区，分区的节点不用再参与左边或者右边的分区，因为这个节点的左边数据都比该节点小，右边数据都比该节点大，所以这个节点是全局有序的，不用参与左右分区。

2、再对0到分区节点-1继续分区；

3、最后对分区节点+1到最后的索引分区；

归并排序：先分左右部分，再合并。

1、获取中间节点；

2、从左边开始节点到中间节点分左右部分；

3、从中间节点+1到右边最后节点分左右部分；

4、合并两个分区的数据。

链表的基本操作：链表反转，找中间节点，判断是否有环。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/547049
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号