3.3插入节点
- 插入一个节点到链表中，首先得判断这个位置是否是合法的，才能进行插入～
- 找到想要插入的位置的上一个节点就可以了～
/** * 插入节点 * * @param head 头指针 * @param index 要插入的位置 * @param value 要插入的值 */ public static void insertNode(Node head, int index, int value) { //首先需要判断指定位置是否合法， if (index < 1 || index > linkListLength(head) + 1) { System.out.println("插入位置不合法。"); return; } //临时节点，从头节点开始 Node temp = head; //记录遍历的当前位置 int currentPos = 0; //初始化要插入的节点 Node insertNode = new Node(value); while (temp.next != null) { //找到上一个节点的位置了 if ((index - 1) == currentPos) { //temp表示的是上一个节点 //将原本由上一个节点的指向交由插入的节点来指向 insertNode.next = temp.next; //将上一个节点的指针域指向要插入的节点 temp.next = insertNode; return; } currentPos++; temp = temp.next; } }
3.4获取链表的长度
获取链表的长度就很简单了，遍历一下，每得到一个节点+1即可～
/** * 获取链表的长度 * @param head 头指针 */ public static int linkListLength(Node head) { int length = 0; //临时节点，从首节点开始 Node temp = head.next; // 找到尾节点 while (temp != null) { length++; temp = temp.next; } return length; }
3.5删除节点
删除某个位置上的节点其实是和插入节点很像的， 同样都要找到上一个节点。将上一个节点的指针域改变一下，就可以删除了～
/** * 根据位置删除节点 * * @param head 头指针 * @param index 要删除的位置 */ public static void deleteNode(Node head, int index) { //首先需要判断指定位置是否合法， if (index < 1 || index > linkListLength(head) + 1) { System.out.println("删除位置不合法。"); return; } //临时节点，从头节点开始 Node temp = head; //记录遍历的当前位置 int currentPos = 0; while (temp.next != null) { //找到上一个节点的位置了 if ((index - 1) == currentPos) { //temp表示的是上一个节点 //temp.next表示的是想要删除的节点 //将想要删除的节点存储一下 Node deleteNode = temp.next; //想要删除节点的下一个节点交由上一个节点来控制 temp.next = deleteNode.next; //Java会回收它，设置不设置为null应该没多大意义了(个人觉得,如果不对请指出哦～) deleteNode = null; return; } currentPos++; temp = temp.next; } }
3.6对链表进行排序
前面已经讲过了8种的排序算法了【八种排序算法总结】，这次挑简单的冒泡排序吧(其实我是想写快速排序的，尝试了一下感觉有点难…..)
/** * 对链表进行排序 * * @param head * */ public static void sortLinkList(Node head) { Node currentNode; Node nextNode; for (currentNode = head.next; currentNode.next != null; currentNode = currentNode.next) { for (nextNode = head.next; nextNode.next != null; nextNode = nextNode.next) { if (nextNode.data > nextNode.next.data) { int temp = nextNode.data; nextNode.data = nextNode.next.data; nextNode.next.data = temp; } } } }
3.7找到链表中倒数第k个节点
这个算法挺有趣的：设置两个指针p1、p2，让p2比p1快k个节点，同时向后遍历，当p2为空，则p1为倒数第k个节点
/** * 找到链表中倒数第k个节点(设置两个指针p1、p2，让p2比p1快k个节点，同时向后遍历，当p2为空，则p1为倒数第k个节点 * * @param head * @param k 倒数第k个节点 */ public static Node findKNode(Node head, int k) { if (k < 1 || k > linkListLength(head)) return null; Node p1 = head; Node p2 = head; // p2比怕p1快k个节点 for (int i = 0; i < k - 1; i++) p2 = p2.next; // 只要p2为null，那么p1就是倒数第k个节点了 while (p2.next != null) { p2 = p2.next; p1 = p1.next; } return p1; }
3.8删除链表重复数据
跟冒泡排序差不多，只要它相等，就能删除了～
/** * 删除链表重复数据(跟冒泡差不多，等于删除就是了) * * @param head 头节点 */ public static void deleteDuplecate(Node head) { //临时节点，(从首节点开始-->真正有数据的节点) Node temp = head.next; //当前节点(首节点)的下一个节点 Node nextNode = temp.next; while (temp.next != null) { while (nextNode.next != null) { if (nextNode.next.data == nextNode.data) { //将下一个节点删除(当前节点指向下下个节点) nextNode.next = nextNode.next.next; } else { //继续下一个 nextNode = nextNode.next; } } //下一轮比较 temp = temp.next; } }
3.9查询链表的中间节点
这个算法也挺有趣的：一个每次走1步，一个每次走两步，走两步的遍历完，然后走一步的指针，那就是中间节点
/** * 查询单链表的中间节点 */ public static Node searchMid(Node head) { Node p1 = head; Node p2 = head; // 一个走一步，一个走两步，直到为null，走一步的到达的就是中间节点 while (p2 != null && p2.next != null && p2.next.next != null) { p1 = p1.next; p2 = p2.next.next; } return p1; }
3.10通过递归从尾到头输出单链表
/** * 通过递归从尾到头输出单链表 * * @param head 头节点 */ public static void printListReversely(Node head) { if (head != null) { printListReversely(head.next); System.out.println(head.data); } }
3.11反转链表
/** * 实现链表的反转 * * @param node 链表的头节点 */ public static Node reverseLinkList(Node node) { Node prev ; if (node == null || node.next == null) { prev = node; } else { Node tmp = reverseLinkList(node.next); node.next.next = node; node.next = null; prev = tmp; } return prev; }
反转链表参考自：
四、最后
理解链表本身并不难，但做相关的操作就弄得头疼，
head.next next next next ....(算法这方面我还是薄弱啊..脑子不够用了…..)写了两天就写了这么点东西…
操作一个链表只需要知道它的头指针就可以做任何操作了
- 添加数据到链表中
- 遍历找到尾节点，插入即可(只要
while(temp.next != null)，退出循环就会找到尾节点)
- 遍历链表
- 从首节点(有效节点)开始，只要不为null，就输出
- 给定位置插入节点到链表中
- 将原本由上一个节点的指向交由插入的节点来指向
- 上一个节点指针域指向想要插入的节点
- 首先判断该位置是否有效(在链表长度的范围内)
- 找到想要插入位置的上一个节点
- 获取链表的长度
- 每访问一次节点，变量++操作即可
- 删除给定位置的节点
- 将原本由上一个节点的指向后面一个节点
- 首先判断该位置是否有效(在链表长度的范围内)
- 找到想要插入位置的上一个节点
- 对链表进行排序
- 使用冒泡算法对其进行排序
- 找到链表中倒数第k个节点
- 设置两个指针p1、p2，让p2比p1快k个节点，同时向后遍历，当p2为空，则p1为倒数第k个节点
- 删除链表重复数据
- 操作跟冒泡排序差不多，只要它相等，就能删除了～
- 查询链表的中间节点
- 这个算法也挺有趣的：一个每次走1步，一个每次走两步，走两步的遍历完，然后走一步的指针，那就是中间节点
- 递归从尾到头输出单链表
- 只要下面还有数据，那就往下找，递归是从最后往前翻。
- 反转链表
- 有递归和非递归两种方式，我觉得是挺难的。可以到我给出的链接上查阅～
PS：每个人的实现都会不一样，所以一些小细节难免会有些变动，也没有固定的写法，能够实现功能即可～
参考资料：
