• 单链表和双链表

    单链表和双链表

    单链表：只有一个指向下一节点的指针   -->  单向读取

    双链表：既有指向下一节点的指针，也有指向上一节点的指针，可以通过此向前查找

    单链表和双链表的反转：逆序

    整个链表逆序、部分链表逆序

    是否需要返回值

    链表的反转需要换头（整个链表逆序）的操作，则需要返回值（需要一个Node类型的返回值，存储换头之后的head值）

    单链表的逆序及部分链表的逆序

    注：当head为整个链表的头结点时，pre初始值为null，next指针反转之后head头节点指向pre，也就是null 

    1. package linkedlist;
    2.  
    3. public class SingleLinkedList {
    4.  
    5.     class Node {
    6.         public int value;
    7.         public Node next;
    8.  
    9.         public Node(int data) {
    10.             this.value = data;
    11.         }
    12.  
    13.     }
    14.  
    15.     //单链表的反转
    16.     //单链表的反转只需要将指针的方向反转，在逆序整个链表的时候，用head遍历链表的所有结点，使得每个指针由后一结点指向前一结点
    17.     public static Node reverseList(Node head) {//head传入时是链表的头结点，在循环中为当前结点
    18.         Node pre = null;//处理的结点的前一个结点
    19.         Node next = null;//处理的结点的后一个结点
    20.         while (head != null) {
    21.             next = head.next;//head的后一个结点
    22.             head.next = pre;//反转指针
    23.             pre = head;
    24.             head = next;
    25.         }
    26.         return pre;//出循环时head==null，pre为整个链表的最后一个结点，也就是链表反转之后的头
    27.     }
    28.  
    29.     //部分单链表的反转
    30.     //这里说部分反转应当是不需要返回值的，但是取的不同的start和end数值，可能会导致链表的头改变，需要返回值，因此返回
    31.     public static Node reverselistPart(Node head, int start, int end) {//head为当前结点,starthe end为起始位置
    32.         Node startNode = null;
    33.         Node endNode = null;
    34.         int length = 0;//因为链表与数组不同，不能够直到当前结点在整个链表之间的位置，需要计数
    35.         Node pre = head;
    36.  
    37.         //遍历整个链表，此时pre指的是当前结点
    38.         while (pre != null) {//获得整个链表的长度
    39.             length++;
    40.             //找到startNode节点的前一个结点
    41.             if (length == start - 1) {
    42.                 startNode = pre;
    43.             }
    44.             //找到endNode节点的后一个节点
    45.             if (length == end + 1) {
    46.                 endNode = pre;
    47.             }
    48.             pre = pre.next;//遍历，避免死循环
    49.         }
    50.  
    51.  
    52.         //判断所给的start和end是否合理
    53.         if (start < 1 || end > length || start >= end) {
    54.             return head;//不合理的数视为不对链表进行逆序
    55.         } else if (startNode == null) {//start==1,反转的部分包含头结点
    56.             pre = head;
    57.         } else {
    58.             pre = startNode.next;
    59.         }
    60.  
    61.  
    62.         //反转startNode和后一个结点
    63.         //pre为开始结点的下一个结点，headNode为pre结点的下一个结点
    64.         Node headNode = pre.next;
    65.         pre.next = startNode;//next指针由pre指向startNode，实现指针的反转
    66.  
    67.         Node next = null;
    68.  
    69.  
    70.         //反转从startNode后一个结点到endNode的前一个结点中所有的结点
    71.         while (headNode != endNode) {//链表的反转
    72.             next = headNode.next;
    73.             headNode.next = pre;
    74.             pre = headNode;
    75.             headNode = next;
    76.         }
    77.  
    78. //        if (startNode != null) {
    79. //            startNode.next = pre;
    80. //            return headNode;
    81. //        }
    82.  
    83.         return pre;
    84.     }
    85. }
    86.  
    87.

    双链表的逆序

    双链表的逆序和单链表相同，但是需要反转pre和next两个指针

    1. package linkedlist;
    2.  
    3. class DoubleNode {
    4.     public DoubleNode(int data) {
    5.         this.value = data;
    6.     }
    7.  
    8.     public int value;
    9.     public DoubleNode next;
    10.     public DoubleNode pre;
    11.  
    12.     public static DoubleNode reverseList(DoubleNode head) {
    13.         DoubleNode pre = null;
    14.         DoubleNode next = null;
    15.         while (head != null) {
    16.             next = head.next;
    17.             head.next = pre;
    18.             head.pre = next;
    19.             pre = head;
    20.             head = next;
    21.         }
    22.         return pre;
    23.     }
    24. }
    25.

    打印两个有序链表的公共部分

    判断一个链表是否是一个回文结构

    1、将链表结构放到栈中，比较栈弹出的顺序是否与原序相同（栈先进后出），全部相同则是回文

          O(n)的额外空间

    1. package linkedlist;
    2.  
    3. import java.util.Stack;
    4.  
    5. public class IsPalindromic {
    6.     class Node {
    7.         public int value;
    8.         public Node next;
    9.  
    10.         public Node(int data) {
    11.             this.value = data;
    12.         }
    13.     }
    14.  
    15.     public static boolean isplindromicbyStack(Node head) {
    16.         Stack<Node> stack = new Stack<Node>();//创建栈结构
    17.  
    18.         Node temp = head;
    19.         while (temp != null) {
    20.             stack.push(temp);//入栈
    21.             temp = temp.next;
    22.         }
    23.         
    24.         while (head != null){
    25.             if(head.value != stack.pop().value){//出栈，判断前后顺序是否相同
    26.                 return false;
    27.             }
    28.             head = head.next;
    29.         }
    30.         return true;
    31.     }
    32. }

    2、优化：降低空间复杂度

          O(n/2)的额外空间

    将右半部分的链表放到栈中，从链表左侧开始遍历，每遍历一个栈弹出一个，一一进行比较，全部相同则回文       

            单链表无法获知整个链表有多少数，单指针无法判断此时经历的结点是否是链表结构的一半

            快慢指针：快指针一次走2步，慢指针一次走1步；当快指针遍历完整个链表，慢指针走到中点

            在实际情况中快慢指针需要根据题目调整代码

    1. public static boolean isplindromicbyfastandslowPointer(Node head){
    2.         if(head == null || head.next == null){
    3.             return true;//整个链表为空或是只有一个Node也被视为回文结构
    4.         }
    5.  
    6.         //快慢指针
    7.         Node slow = head.next;
    8.         Node fast = head;
    9.  
    10.         //整个链表为偶数时，慢指针位于n/2位置上；奇数时，整个链表位于n/2位置向上取整+1（5 - 4）
    11.         while(fast.next != null && fast.next.next != null){
    12.             slow = slow.next;
    13.             fast = fast.next.next;
    14.         }
    15.  
    16.        //取出后半段入栈
    17.         Stack<Node> stack = new Stack<Node>();
    18.         while(slow != null){
    19.             stack.push(slow);
    20.             slow = slow.next;
    21.         }
    22.         
    23.         //将后半段与前半段比较，是否相同
    24.         while(!stack.isEmpty()){
    25.             if(head.value != stack.pop().value){
    26.                 return false;
    27.             }
    28.             head = head.next;
    29.         }
    30.         return true;
    31.     }

    3、优化：不使用额外的数据结构

          O(1)的额外空间

    快指针一次走2步，慢指针一次走1步；慢指针走到中间的位置，遍历后面部分的链表逆序；

    两个指针，一个从head向后遍历，一个从end向前遍历，直到一个指针指向空

    1. public static boolean isplindromicbytwoPointer(Node head) {
    2.         if (head == null || head.next == null) {
    3.             return true;//整个链表为空或是只有一个Node也被视为回文结构
    4.         }
    5.  
    6.         Node slow = head;
    7.         Node fast = head;
    8.         while (fast.next != null && fast.next.next != null) {
    9.             slow = slow.next;//最后到达中点位置，奇数时中点位置向上取整
    10.             fast = fast.next.next;//最后到达链表最后一位或两位
    11.         }
    12.  
    13.         fast = slow.next;//从右半部分的起点开始
    14.         slow.next = null;//空出空间便于后半部分逆序
    15.  
    16.         //后半部分逆序
    17.         Node temp = null;
    18.         while (fast != null) {
    19.             temp = fast.next;
    20.             fast.next = slow;//反转指针
    21.             slow = fast;
    22.             fast = temp;
    23.         }
    24.         temp = slow;//slow为反转部分的最后一个结点，也就是后半部分反转部分的头
    25.         fast = head;//左半部分的头
    26.  
    27.         boolean res = true;
    28.         //slow表示右半部分，fast表示左半部分
    29.         while (slow != null && fast != null) {
    30.             if (slow.value != fast.value) {
    31.                 res = false;
    32.                 break;
    33.             }
    34.             slow = slow.next;
    35.             fast = fast.next;
    36.         }
    37.  
    38.         //将链表反转回去  slow -- fast ,  temp -- slow , fast -- temp
    39.         slow = temp.next;
    40.         temp.next = null;
    41. //      fast = slow.next;
    42. //      slow.next = null;
    43.         
    44.         while (slow != null) {
    45. //      while (fast != null)
    46.  
    47.             fast = slow.next;
    48.             slow.next = temp;
    49.             temp = slow;
    50.             slow = fast;
    51. //          temp = fast.next;
    52. //          fast.next = slow;//反转指针
    53. //          slow = fast;
    54. //          fast = temp;
    55.         }
    56.         
    57.         return res;
    58.     }

    将单链表按某值划分为左边小、中间相等、右边大的形式

    使用额外空间：将单链表的每个结点放到数组中，对数组进行partition操作（左边小、中间相等、右边大） 

    不使用额外空间：六个变量，分别为小于、等于、大于部分的头和尾

    注：三区域串起来的时候需要注意区域是否存在，否则会指向null导致出错 

    1. package linkedlist;
    2.  
    3. public class ListPartition {
    4.     class Node {
    5.         public int value;
    6.         public Node next;
    7.  
    8.         public Node(int data) {
    9.             this.value = data;
    10.         }
    11.     }
    12.  
    13.  
    14.     public static Node listPattition(Node head, int pivot) {
    15.         Node SH = null;
    16.         Node ST = null;
    17.         Node EH = null;
    18.         Node ET = null;
    19.         Node BH = null;
    20.         Node BT = null;
    21.         Node temp = null;
    22.  
    23.         while (head != null) {
    24.             temp = head.next;//存储下一个head
    25.             head.next = null;//消去指针
    26.  
    27.  
    28.             if (head.value < pivot) {
    29.                 if (SH == null) {
    30.                     SH = head;
    31.                     ST = head;
    32.                 } else {
    33.                     ST.next = head;
    34.                     ST = head;
    35.                 }
    36.             }
    37.             if (head.value == pivot) {
    38.                 if (EH == null) {
    39.                     EH = head;
    40.                     ET = head;
    41.                 } else {
    42.                     ET.next = head;
    43.                     ET = head;
    44.                 }
    45.             }
    46.             if (head.value > pivot) {
    47.                 if (BH == null) {
    48.                     BH = head;
    49.                     BT = null;
    50.                 } else {
    51.                     BT.next = head;
    52.                     BT = head;
    53.                 }
    54.             }
    55.  
    56.             head = temp;//再次进行赋值，使得head遍历整个链表
    57.         }
    58.  
    59.         if (ST != null) {//有小于区域
    60.             if (ET != null) {//有等于区域
    61.                 ST.next = EH;
    62.             } else if (BT != null) {//没有等于区域，有大于区域
    63.                 ST.next = BH;
    64.             } else {//啥也没有
    65.                 ST.next = null;
    66.             }
    67.         }
    68.  
    69.         if (ET != null) {//有等于区域
    70.             if (BT != null) {//有大于区域
    71.                 ET.next = BH;
    72.             } else {//无大于区域
    73.                 ET.next = null;
    74.             }
    75.         }
    76.         
    77.         //最终返回结果
    78.         if(ST != null){
    79.             return SH;
    80.         } else if (ET != null) {
    81.             return EH;
    82.         }else{
    83.             return BH;
    84.         }
    85.     }
    86. }

    复制含有随机指针节点的链表

    使用额外空间：哈希表拷贝节点，通过原来的节点1的next指针找到节点2，拷贝后的节点1'对应节点2'，由此可知节点1'的next指针指向节点2'。random指针同理。

    不使用额外空间：在链表的每个节点后插入其对应拷贝节点，通过节点1的next指针找到拷贝的节点1'，节点1的random指针指向节点3，节点3的next指针指向节点3'，由此可以拷贝节点1'指向节点3'的random指针

    由next指针向下遍历，将每一对的指针都拷贝出，拷贝所有的random指针后抽离出拷贝的链表（画的好丑）

    1. package linkedlist;
    2.  
    3. public class CopyLinkedListWithRand {
    4.     class Node {
    5.         public int value;
    6.         public Node next;
    7.         public Node rand;
    8.  
    9.         public Node(int data) {
    10.             this.value = data;
    11.         }
    12.  
    13.     }
    14.  
    15.     public Node copylistwithRand(Node head) {
    16.         if (head == null) {
    17.             return null;
    18.         }
    19.  
    20.         Node node1 = head;
    21.         Node node2 = null;
    22.  
    23.         //1 -> 2  
    24.         //1 -> 1' -> 2
    25.         while (node1 != null) {
    26.             node2 = node1.next;
    27.             node1.next = new Node(node1.value);//克隆的新节点
    28.             node1.next.next = node2;
    29.             node1 = node2;
    30.         }
    31.         
    32.         node1 = head;//重新来过
    33.         
    34.         //拷贝random指针
    35.         while (node1 != null) {
    36.             
    37.             if (node1.rand != null) {//节点1的random指针
    38.                 node1.next.rand = node1.rand.next;//节点1'的random指针=节点3的next=节点3'
    39.             } else {
    40.                 node1.next.rand = null;
    41.             }
    42.  
    43.             node1 = node1.next.next;
    44.         }
    45.         
    46.         Node res = head.next;//拷贝出来的链表的头节点
    47.         node1 = head;//再次重新来过
    48.         Node temp = res;
    49.         
    50.         while(node1 != null){
    51.             node1 = node1.next.next;//跳到第三个，第五个...
    52.             if(node1.next != null) {
    53.                 temp.next = node1.next;//第二个指向第四个，第四个指向第六个...
    54.             }else{
    55.                 temp.next = null;
    56.             }
    57.             temp = temp.next;//第二个跳第四个，第四个跳第六个...
    58.         }
    59.  
    60.         return res;//返回拷贝链表的头
    61.     }
    62. }

  • 相关阅读:
    [笔记]攻防工具分享之 CobaltStrike框架 《二》生成后门
    DTS搭载全新自研内核，突破两地三中心架构的关键技术｜腾讯云数据库
    自主品牌首次「赶超」合资，中国供应商「突围」智能电动赛道
    Qt的WebEngineView加载网页时出现Error: WebGL is not supported
    云安全-云服务器(RAM)后渗透
    56.【全局变量和局部变量专题】
    034：vue项目利用qrcodejs2生成二维码示例
    基于SSM的图书智能推荐销售系统
    Qt入门（零）——Qt概述
    大数据学习之Spark基础
  • 原文地址：https://blog.csdn.net/m0_73530538/article/details/132661280