03、数据结构与算法--单向链表

一种比顺序表稍微复杂些的结构...一、认识链表1、基本结构链表是一个个结点构成的就像火车顺序表可以通过get方法(传入下标)来获取表因为它们的地址是连续的与顺序表不同的是链表的物理存储不连续要获取某个结点的话不得不进行遍历2、手动实现注意 1、先绑定后面结点2、遍历时注意是cur ! null还是cur.next ! nullpackage structure; public class MyLinkedList { public Node head; //结点类 class Node { public int val; public Node next; public Node(int val) { this.val val; } } // 傻瓜式创建展示一下链表结构 // public void createList () { // // Node node1 new Node(12); // Node node2 new Node(24); // Node node3 new Node(36); // Node node4 new Node(48); // Node node5 new Node(50); // // node1.next node2; // node2.next node3; // node3.next node4; // node4.next node5; // // this.head node1; // // } //打印链表val值 public void show () { Node cur head; while (cur ! null) { System.out.print(cur.val ); cur cur.next; } System.out.println(); } //从传入的head开始遍历 public void show (Node newhead) { Node cur newhead; while (cur ! null) { System.out.print(cur.val ); cur cur.next; } System.out.println(); } //头插法 public void addFirst(int data) { Node n new Node(data); n.next head; head n; } //尾插法 public void addLast(int data) { Node n new Node(data); if (head null){ head n; //此处没有return会继续执行下面的内容 return; } Node cur head; while (cur.next ! null){ cur cur.next; } cur.next n; } //将数据插入到下标index位置 public void addIndex(int index, int data) { //这样就不用重复调用方法了 int len size(); if(index 0 || index len){ System.out.println(index位置不合法); return; } //插在最前 if (index 0){ addFirst(data); return; } //插到最后 if (index len){ addLast(data); return; } //代表index位置的前一位 Node curN head; // 此写法可读性较差 // int count index; // while (count - 1 ! 0){ // cur cur.next; // count--; // } //找到index的前一位curN for (int i 0;i index-1;i){ curN curN.next; } Node n new Node(data); //主要逻辑 n.next curN.next; curN.next n; } //查找key值是否在单链表当中 public boolean contains(int key) { Node cur head; while (cur ! null){ if (cur.val key){ return true; } cur cur.next; } return false; } // //删除遇见的第一个值为key的节点 // public void remove(int key) { // // Node cur head; // Node del findDel(key); // // //确保头结点不为空 // if(head null){ // return; // } // //删除头结点 // if(head del){ // head head.next; // return; // } // // //优先选择引用比较比值比较更安全 // while (cur ! del){ // cur cur.next; // } // // //主要逻辑 // cur.next del.next; // // } // // //找到要删除结点del的地址 // public Node findDel(int key){ // // Node i head; // // while (i ! null){ // if (i.val key){ // return i; // } // i i.next; // } // return null; // // } //删除遇见的第一个值为key的节点 public void remove(int key) { //确保头结点不为空 if(head null){ return; } //删除头结点 if(head.val key){ head head.next; return; } Node prev head; Node del prev.next; //优先选择引用比较比值比较更安全 while (prev.next ! null){ if (del.val key){ //主要逻辑 prev.next del.next; return; } prev prev.next; } } //删除所有值为key的节点 public void removeAllKey(int key) { // //先循环处理头结点可能连续多个 // while (head ! null head.val key){ // head head.next; // } // //链表为空直接返回 if (head null){ return; } Node prev head; Node del prev.next; //主要逻辑 while (del ! null){ if(del.val key){ del del.next; prev.next del; }else { del del.next; prev prev.next; } } //最后再处理头结点写法更为简洁 if (head.val key){ head head.next; } } //得到单链表结点的数量 public int size() { int count 0; Node cur head; while (cur ! null){ count; cur cur.next; } return count; } //反转链表 //从传入的newHead头结点开始反转链表 public Node reverseList(Node newHead) { if(newHead null){ return newHead; } //确定cur位置将传入的头结点next置空 Node cur newHead.next; newHead.next null; Node curN; while(cur ! null){ //保存cur下一个结点的值然后再修改指向 curN cur.next; cur.next newHead; //newHead接着往下走cur来到curN位置 newHead cur; cur curN; } return newHead; } //找到链表的中间结点 public Node middleNode(Node head) { Node fast head; Node slow head; while(fast ! null fast.next ! null){ fast fast.next.next; slow slow.next; } return slow; } //返回倒数第k个结点的值 public int kthToLast(Node head, int k) { Node fast head; Node slow head; int count 0; while(count ! k-1){ fast fast.next; count; } while(fast.next ! null){ fast fast.next; slow slow.next; } return slow.val; } //清空 public void clear() { head null; } public static void main (String[]args){ MyLinkedList x new MyLinkedList(); //x.createList(); x.addFirst(67); x.addFirst(24); x.addFirst(8888); x.addFirst(48); x.addFirst(24); x.show(); int a x.kthToLast(x.head,3); System.out.println(a); } }3、重要方法的逻辑图①头插法②尾插法③指定位置插入中间元素这里要找到index的前一位curN来完成后续绑定④删除遇见的第一个值为key的结点遇见key删除后直接返回没遇见仅prev继续往下走⑤删除所有值为key的结点也是面试题目遇见要删除的key值执行删除逻辑没遇见要删除的key值key跟prev都继续往下走del一直走过最后一个结点停止这里的prev一直充当del的前置结点直到中间结点处理完以后再处理头结点二、链表的面试题1、反转链表2、分割链表Ⅰ代码解析①//反转链表 //从传入的newHead头结点开始反转链表 public Node reverseList(Node newHead) { if(newHead null){ return newHead; } //确定cur位置将传入的头结点next置空 Node cur newHead.next; newHead.next null; Node curN; while(cur ! null){ //保存cur下一个结点的值然后再修改指向 curN cur.next; cur.next newHead; //newHead接着往下走cur来到curN位置 newHead cur; cur curN; } return newHead; }如果想接收返回的头结点完全可以定义一个show的重载方法//从传入的head开始遍历 public void show (Node newhead) { Node cur newhead; while (cur ! null) { System.out.print(cur.val ); cur cur.next; } System.out.println(); }最后调用即可public static void main (String[]args){ MyLinkedList x new MyLinkedList(); x.addFirst(67); x.addFirst(24); x.addFirst(48); x.addFirst(24); x.show(); System.out.println(); Node a x.reverseList(x.head); x.show(a); }②public Node partition(Node head, int x) { // 1、初始化变量 Node bs null; Node be null; Node as null; Node ae null; // 2、定义 cur 并初始化 Node cur head; // 3、遍历链表 while(cur ! null) { if(cur.val x) { // 处理小于 x 的节点 if(bs null) { bs cur; be cur; } else { be.next cur; be be.next; } } else { // 处理大于等于 x 的节点 if(as null) { as cur; ae cur; } else { ae.next cur; ae ae.next; } } // 4、移动指针 cur cur.next; } // 5、连接两条链 if(bs null) { return as; } be.next as; //6、找到最后结点置空 if(ae ! null){ ae.next null; } return bs; }测试用例:public static void main (String[]args){ LinkPlus x new LinkPlus(); //x.createList(); x.addFirst(67); x.addFirst(24); x.addFirst(8888); x.addFirst(48); x.addFirst(24); x.show(); //没有小于的就返回原链表 x.show(x.partition(x.head,24)); }Ⅱ逻辑图解①⬇️⬇️②这两道相对简单些3、链表的中间结点4、返回倒数第k个结点Ⅰ代码解析③//找到链表的中间结点 public Node middleNode(Node head) { Node fast head; Node slow head; //奇偶兼容 while(fast ! null fast.next ! null){ fast fast.next.next; slow slow.next; } return slow; }想要从slow为头向后打印与上面题目同理public static void main (String[]args){ MyLinkedList x new MyLinkedList(); //x.createList(); x.addFirst(67); x.addFirst(24); x.addFirst(8888); x.addFirst(48); x.addFirst(24); x.show(); Node cur x.middleNode(x.head); x.show(cur); }④//返回倒数第k个结点的值 public int kthToLast(Node head, int k) { Node fast head; Node slow head; int count 0; // if(k 0){ return -1; } while(count ! k-1){ fast fast.next; //写在这里就不用在前面写k size少一次遍历 if(fast null){ return -1; } count; } while(fast.next ! null){ fast fast.next; slow slow.next; } return slow.val; }测试用例public static void main (String[]args){ MyLinkedList x new MyLinkedList(); //x.createList(); x.addFirst(67); x.addFirst(24); x.addFirst(8888); x.addFirst(48); x.addFirst(24); x.show(); int a x.kthToLast(x.head,3); System.out.println(a); }Ⅱ逻辑图解③④本章完