单链表常用算法

文章目录

• ​​单链表​​
• ​​单链表经典算法题​​

• ​​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;
    }