单链表常用算法

文章目录

单链表单链表经典算法题1.删除链表中等于给定值 val 的所有节点。2.返回链表的中间节点3.删除指定节点4.删除链表中的重复元素5.反转链表6.删除倒数第n个节点

单链表

单链表是一种包含一个指向后继节点的指针和数据域

/** * 节点类 */ public class ListNode { int val; ListNode next; ListNode(int x) { val = x; } }

单链表经典算法题

1.删除链表中等于给定值 val 的所有节点。

示例:

输入: 1->2->6->3->4->5->6, val = 6

输出: 1->2->3->4->5

直接操作链表

/** * 删除链表中指定值的节点 ---> 【双指针】 * @param head * @param val * @return */ public ListNode removeElements(ListNode head, int val) { if(head == null){ return null; } //要删除的是第一个节点 while(head.val == val){ head = head.next; if(head == null){ return null; } } //其他情况 //当前指针，指向当前节点 ListNode curNode = head.next; //前驱指针，指向当前节点的前驱节点 ListNode preNode = head; while(curNode != null){ if(curNode.val == val){ //前节点的后继节点变成当前节点的后继节点 preNode.next = curNode.next; curNode = curNode.next; }else{ preNode = preNode.next; curNode = curNode.next; } } return head; }

递归解法

/** * 删除链表中指定值的节点 ---> 【递归】 * @param head * @param val * @return */ public ListNode removeElements2(ListNode head, int val) { if(head != null){ head.next = removeElements(head.next,val); return head.val == val ? head.next:head; } return head; }

2.返回链表的中间节点

给定一个带有头结点 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

快慢指针

/** * 返回链表的中间节点 ----> 【快慢指针】 * @param head * @return */ public ListNode middleNode(ListNode head) { if (head ==null || head.next == null){ return head; } ListNode slow = head; ListNode fast = head; while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; } return slow; }

计算链表长度，然后返回从中间节点开始的序列

/** * 返回链表的中间节点 ----> 【计算链表长度，然后返回从中间节点开始的序列】 * @param head * @return */ public ListNode middleNode2(ListNode head) { int len = 0; ListNode q = head; while(q != null){ len++; q = q.next; } int temp = 0; ListNode node = head; while(node != null){ temp++; if(temp == len/2+1){ break; } node = node.next; } return node; }

3.删除指定节点

/** * 删除指定节点(单链表) ---> 【直接覆盖】 * 时间复杂度：O(1) * 空间复杂度：O(1) * @param node */ public void deleteNode(ListNode node) { //后继节点覆盖node node.val = node.next.val; node.next = node.next.next; }

4.删除链表中的重复元素

/** * 删除链表中的重复元素(单链表) 【单指针】 * 时间复杂度：O(N) * 空间复杂度：O(1) * @param head * @return */ public ListNode deleteDuplicates(ListNode head) { if(head == null){ return null; } //有序链表直接遍历即可 ListNode node = head; while(node.next != null){ if(node.val == node.next.val){ node.next = node.next.next; }else { node = node.next; } } return head; }

5.反转链表

迭代

/** * 反转链表 【迭代】 * @param head * @return */ public ListNode reverseList(ListNode head) { ListNode newHead = null; ListNode h = head; while(h != null){ ListNode tmp = h.next; h.next = newHead; newHead = h; h = tmp; } //pre:每次指向反转链表的头结点 return newHead; }

递归

/** * 反转链表 【递归】 * @param head * @return */ public ListNode reverseList2(ListNode head) { if(head == null || head.next == null){ return head; } ListNode newHead = reverseList(head.next); //反转过程 head.next.next = head; head.next = null; return newHead; }

6.删除倒数第n个节点

/** * 删除倒数第 n 个节点 * @param head * @param n * @return */ public ListNode removeNthNode(ListNode head,int n){ if(head == null || head.next == null){ return null; } ListNode node = new ListNode(-1); ListNode slow = head; ListNode fast = head; for(int i = 0;i < n+1;i++){ fast = fast.next; } while (fast != null){ fast = fast.next; slow = slow.next; } slow.next = slow.next.next; return node.next; }