#yyds干货盘点# 数据结构与算法学习——单链表相关算法

博观而约取,厚积而薄发。这篇文章主要讲述#yyds干货盘点# 数据结构与算法学习——单链表相关算法相关的知识,希望能为你提供帮助。
@TOC
目录 ?博主介绍::: hljs-center
? 个人主页:苏州凯捷智能科技有限公司
?作者介绍:苏州凯捷智能科技有限公司创始人,主要目前与华为合作5G工业机器人领域开发,2D、3D视觉项目开发,政府项目投标开发。
? 有任何问题欢迎私信,看到会及时回复
微信公众号:苏州程序大白
?想加入技术交流群的可以加我好友,群里会分享学习资料
:::
前言

#yyds干货盘点# 数据结构与算法学习——单链表相关算法

文章图片

使用java实现单链表建立Node节点类的代码如下:
public class Node Integer data; Node next; public Node(Integer data) this.data = https://www.songbingjia.com/android/data; @Override public String toString() return"Node" + "data="https://www.songbingjia.com/android/+ data + ;

【#yyds干货盘点# 数据结构与算法学习——单链表相关算法】建立链表类并编写链表类的添加节点和遍历方法。
public class LinkedList Node head; /*** * 添加节点的方法 * @param node 待添加节点 */ public void addNode(Node node) if(this.head == null) //如果当前头节点为空,那么将传入的节点作为头节点 this.head = node; return; //由于单链表的头节点不可移动,所以我们使用一个临时指针来辅助我们添加节点。 Node temp = head; while(true) if(temp.next == null) break; temp = temp.next; //退出循环时,temp节点指向链表最后一个节点,此时将传入节点挂在temp之后即可 temp.next = node; /*** * 遍历链表的方法 */ public void list() if(this.head == null) System.out.println("链表为空,无法遍历!"); return; Node temp = head; while(true) if(temp == null) break; System.out.println(temp); temp = temp.next;

编写代码实现单链表的反转这里使用递归来完成单链表的反转,这个算法的思路大体如下:
  • 假设现在有一条单链表:1-2-3-4-NULL,在每次进入倒置函数reverse之前,需要对传入的节点进行判断,当传入的节点为空或者传入节点的next指针域为空时,证明该链表不需要反转,直接返回该节点。
  • 当传入节点的指针域不为空时,将该节点的下一个节点的next域指向自己,同时将该节点的next指针域置为空,这样就形成了局部意义上的链表节点反转,由于我们使用了递归,并设置了递归退出条件(当前传入节点为空或者当前传入节点的next指针域为空),所以我们可以使用这个思路,完成对链表的反转。
#yyds干货盘点# 数据结构与算法学习——单链表相关算法

文章图片

实现代码如下:
/*** * * @param head * @return */ public static Node reverse(Node head) if(head == null || head.next == null) //如果进入这个if块中,证明当前head与其之后结点形成的链表不需要反转 //例如1-2-3-4中的4不需要反转,直接返回该节点即可 return head; //如果链表长度大于等于2,进行递归 Node reverseNode = reverse(head.next); //将当前节点下一个节点的next指针域指向自己 head.next.next = head; //将当前节点的next指针域置空 head.next = null; return reverseNode;

创建一个链表:1-2-3-4-5,测试代码与结果如下:
LinkedList linkedList = new LinkedList(); for (int i = 0; i < 5; i++) linkedList.addNode(new Node(i + 1)); System.out.println("反转前:"); linkedList.list(); LinkedList reverseList = new LinkedList(reverse(linkedList.head)); System.out.println("反转后:"); reverseList.list();

运行结果:
#yyds干货盘点# 数据结构与算法学习——单链表相关算法

文章图片

将两个有序单链表合并为一个有序单链表< font color=#03a9f4size=5 face= " 楷体" > 将A链表:1-2-3-null与B链表2-3-6-null合并为一张有序链表,解题思路如下:< font>
  • 新建一个链表temp,然后使用指针遍历AB链表,对每一次遍历出来的节点的data值进行比较,将data值较小的节点从原链表中摘除,然后加到temp链表中,直到有一条链表被摘空。
  • 此时如果A链表被摘空,那么将B链表剩余的节点挂在temp节点的最后面,由于B链表和temp链表本来就是有序的,所以得出的结果仍然是一个有序列表,反之亦然。
代码实现:
/*** * 合并两个有序链表 * @param list1 链表1 * @param list2 链表2 * @return */ public static LinkedList mergeTwoList(LinkedList list1,LinkedList list2) //创建一个 LinkedList temp = new LinkedList(new Node(Integer.MIN_VALUE)); Node cur = temp.head; while(list1.head != null & & list2.head != null) if(list1.head.data < list2.head.data) cur.next = list1.head; list1.head = list1.head.next; else cur.next = list2.head; list2.head = list2.head.next; //每一次循环后都需要将cur后移 cur = cur.next; //退出循环时,至少有一个链表为空 //如果是第一个链表为空,那么将cur.next指向第二个链表的头节点,由于第二个链表本身就是有序的,所以合并后仍然有序 if(list1.head == null) cur.next = list2.head; if(list2.head == null) cur.next = list1.head; //由于temp的第一个节点为MIN_VALUE,为无效节点,所以返回下一个 return new LinkedList(temp.head.next);

测试代码及结果:
LinkedList list1 = new LinkedList(); list1.addNode(new Node(1)); list1.addNode(new Node(2)); list1.addNode(new Node(4)); System.out.println("链表1为:"); list1.list(); LinkedList list2 = new LinkedList(); list2.addNode(new Node(1)); list2.addNode(new Node(3)); list2.addNode(new Node(4)); System.out.println("链表2为:"); list2.list(); LinkedList result = mergeTwoList(list1,list2); System.out.println("合并结果为:"); result.list();

运行结果:
#yyds干货盘点# 数据结构与算法学习——单链表相关算法

文章图片

返回链表中倒数第K个结点返回链表倒数第K个结点,结题思路如下:
  • 创建两个指针beforeafter,并将其指向链表头节点head
  • 先让after结点前进k步,如果在此过程中after结点已经走出链表的范围(即移动过程中after已为空),那么证明输入的k不合法,此时返回null。
  • 完成上一步的操作后,进行循环并使beforeafter同时进行移动,直到after为空时退出循环,此时before指向的元素即为链表的倒数第k个结点。
代码实现:
/*** * 获取链表的倒数第k个结点 * @param list 链表 * @param k * @return */ public static Node getKthFromEnd(LinkedList list,int k) if(list.head == null || list == null || k < 0) return null; Node before = list.head; Node after = list.head; for (int i = 0; i < k; i++) if(after == null) return null; after = after.next; while(after != null) before = before.next; after = after.next; return before;

测试代码以及结果,这里的链表使用上面合并链表的结果:
LinkedList result = mergeTwoList(list1,list2); System.out.println("合并结果为:"); result.list(); System.out.println("倒数第3个结点值为:" + getKthFromEnd(result,2));

运行结果:
#yyds干货盘点# 数据结构与算法学习——单链表相关算法

文章图片


    推荐阅读