Skip to content

链表相关算法

Jump to bottom
zhangpan edited this page Aug 21, 2021 · 27 revisions 
public class ListNode {
    public int val;
    public ListNode next;

    public ListNode() {
    }

    public ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

Leetcode 21. 合并两个有序链表

    /**
     * 解法一：迭代法
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }

        ListNode head;
        if (l1.val <= l2.val) {
            head = l1;
            l1 = l1.next;
        } else {
            head = l2;
            l2 = l2.next;
        }
        ListNode listNode = head;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                listNode.next = l1;
                l1 = l1.next;
            } else {
                listNode.next = l2;
                l2 = l2.next;
            }
            listNode = listNode.next;
        }
        listNode.next = l1 == null ? l2 : l1;

        return head;
    }

    /**
     * 解法二：递归法
     */
    public ListNode mergeTwoList2(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else {
            if (l1.val < l2.val) {
                l1.next = mergeTwoList2(l1.next, l2);
                return l1;
            } else {
                l2.next = mergeTwoList2(l1, l2.next);
                return l2;
            }
        }
    }

Leetcode 24. 两两交换链表中的节点

    // 解法一
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode first = head;
        ListNode second = first.next;
        ListNode temp = second.next;
        head = second;
        while (temp != null && temp.next != null) {
            first.next = temp.next;
            second.next = first;
            first = temp;
            second = first.next;
            temp = second.next;
        }
        first.next = second.next;
        second.next = first;
        return head;
    }
    // 解法二
    public ListNode swapPairs2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = head.next;
        head.next = swapPairs2(newHead.next);
        newHead.next = head;
        return newHead;
    }

LeetCode 61. 旋转链表

解题思路一：让链表成环，然后从head遍历查找，从第k个位置个位置断开。

解题思路二：使用双指针，慢指针指向head，快指针指向k第个节点，然后两个指针指针同时移动，直到快指针的next为null，将慢指针next置为null，将快指针next指向head。

    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode listNode = head;
        int size = 1;
        // 遍历查找最后一个节点
        while (listNode.next != null) {
            listNode = listNode.next;
            size++;
        }
        k = k % size;
        if (k == 0) {
            // 如果移动距离为0，则直接返回head
            return head;
        }
        // 将尾结点指向头结点，构成一个链表环
        listNode.next = head;
        ListNode newHead;
        // 根据k查找断开位置
        for (int i = 0; i < size - k - 1; i++) {
            head = head.next;
        }
        // 头结点
        newHead = head.next;
        // 尾结点指向null
        head.next = null;
        return newHead;
    }

141. 环形链表

// 解法一：双指针
public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }
    ListNode l1 = head;
    ListNode l2 = head;
    while (l1 != null && l2 != null && l2.next != null) {
        l1 = l1.next;
        l2 = l2.next.next;
        if (l1 == l2) {
            return true;
        }
    }
    return false;
}

// 解法二：使用HashSet
public boolean hasCycle2(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }
    HashSet<ListNode> hashSet = new HashSet<>();
    hashSet.add(head);
    while (head != null) {
        head = head.next;
        if (hashSet.contains(head)) {
            return true;
        }
        hashSet.add(head);
    }
    return false;
}

面试题 02.02. 返回倒数第 k 个节点

/**
 * 解法一：使用栈的先进先出特性
 */
public int kthToLast(ListNode head, int k) {
    Stack<ListNode> stackNode = new Stack<>();
    while (head != null) {
        stackNode.push(head);
        head = head.next;
    }
    for (int i = 0; i < k - 1; i++) {
        stackNode.pop();
    }
    return stackNode.pop().val;
}

/**
 * 解法而：遍历链表或得size,然后再找出倒数第k个元素
 */
public int kthToLast2(ListNode head, int k) {
    int size = getListSize(head);
    for (int i = 0; i < size - k; i++) {
        head = head.next;
    }
    return head.val;
}

/**
 * 解法三：双指针
 */
public int kthToLast3(ListNode head, int k) {
    ListNode listNode1 = head;
    ListNode listNode2 = head;
    for (int i = 0; i < k; i++) {
        listNode1 = listNode1.next;
    }
    while (listNode1 != null && listNode1.next != null) {
        listNode1 = listNode1.next;
        listNode2 = listNode2.next;
    }
    return listNode2.val;
}

private int getListSize(ListNode head) {
    int size = 0;
    while (head.next != null) {
        head = head.next;
        size++;
    }
    return ++size;
}

面试题 02.03. 删除中间节点

public void deleteNode(ListNode node) {
    node.val = node.next.val;
    node.next = node.next.next;
}

面试题 02.08. 环路检测

/**
 * 使用HashSet存储Node,对比node是否在HashSet中存在
 */
public ListNode detectCycle(ListNode head) {
    HashSet<ListNode> hashSet = new HashSet<>();
    while (head != null) {
        if (hashSet.contains(head)) {
            return head;
        } else {
            hashSet.add(head);
            head = head.next;
        }
    }
    return null;
}

/**
 * 快慢指针，慢指针一次走一步，快指针一次走两步。
 */
public ListNode detectCycle2(ListNode head) {
    if (head == null || head.next == null) {
        return null;
    }
    ListNode listNode1 = head;
    ListNode listNode2 = head;
    while (listNode1.next != null && listNode2 != null && listNode2.next != null) {
        listNode1 = listNode1.next;
        listNode2 = listNode2.next.next;
        if (listNode1 == listNode2) {
            ListNode ptr = head;
            while (ptr != listNode1) {
                ptr = ptr.next;
                listNode1 = listNode1.next;
            }
            return ptr;
        }
    }
    return null;
}

Leetcode 234. 回文链表

/**
 * 复制链表，双指针校验
 * @param head
 * @return
 */
public boolean isPalindrome(ListNode head) {
    if (head == null) {
        return false;
    }
    if (head.next == null) {
        return true;
    }
    List<Integer> list = new ArrayList<>();
    while (head != null) {
        list.add(head.val);
        head = head.next;
    }

    int left = 0, right = list.size() - 1;
    while (left < right) {
        if (!list.get(left).equals(list.get(right))) {
            return false;
        } else {
            left++;
            right--;
        }
    }
    return true;
}

/**
 * 将后半段链表反转，跟前半段对比
 */
public boolean isPalindrome2(ListNode head) {
    if (head == null) {
        return false;
    }
    if (head.next == null) {
        return true;
    }

    int size = 0;
    ListNode node = head;
    while (node != null) {
        node = node.next;
        size++;
    }

    int halfStart = size % 2 == 0 ? size / 2 : size / 2 + 1;
    int i = 0;
    ListNode halfNode = head;
    while (i < halfStart) {
        halfNode = halfNode.next;
        i++;
    }
    ListNode reverseNode = reverseNode(halfNode);

    while (reverseNode != null) {
        if (head.val != reverseNode.val) {
            return false;
        }
        head = head.next;
        reverseNode = reverseNode.next;
    }
    return true;
}

private ListNode reverseNode(ListNode node) {
    if (node == null || node.next == null) {
        return node;
    }
    ListNode lastNode = reverseNode(node.next);
    node.next.next = node;
    node.next = null;
    return lastNode;
}

Leetcode 445. 两数相加 II

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    Stack<ListNode> stack1 = new Stack<>();
    Stack<ListNode> stack2 = new Stack<>();
    while (l1 != null) {
        stack1.push(l1);
        l1 = l1.next;
    }
    while (l2 != null) {
        stack2.push(l2);
        l2 = l2.next;
    }
    int n = 0;
    ListNode head = null;
    while (!stack1.isEmpty() || !stack2.isEmpty()) {
        int sum = n;
        ListNode node = null;
        if (!stack1.isEmpty()) {
            node = stack1.pop();
            sum += node.val;
        }
        if (!stack2.isEmpty()) {
            node = stack2.pop();
            sum += node.val;
        }
        node.val = sum % 10;
        node.next = head;
        head = node;
        n = sum / 10;
    }
    if (n != 0) {
        ListNode node = new ListNode(n);
        node.next = head;
        return node;
    }
    return head;
}

链表反转相关题

206. 反转链表

/**
 * 递归法
 * 递归的递流程直接找到递归的最后一个节点，最后一个节点的next为null,返回自身，然后开始递归的归流程
 * 递归的归流程，从最后一个节点向上回溯，将最后一个节点的next指向倒数第二个节点，倒数第二个节点的next指向null
 * 以此回溯到第一个节点完成链表的反转
 */
public static ListNode reverseLink2(ListNode head) {
    // head == null这个条件一定要判断啊！！！！
    if (head == null || head.next == null) {
        return head;
    }
    // 返回最后一个节点
    ListNode lastNode = reverseLink2(head.next);
    head.next.next = head;
    head.next = null;
    return lastNode;
}

206 反转链表 扩展

public static ListNode cursor;

public static ListNode reverseLink(ListNode head, int n) {
    if (n == 1) {
        cursor = head.next;
        return head;
    }
    ListNode lastNode = reverseLink(head.next, n - 1);
    head.next.next = head;
    head.next = cursor;
    return lastNode;
}

92. 反转链表 II

public ListNode reverseBetween(ListNode head, int left, int right) {
    if (head == null || head.next == null) {
        return head;
    }
    return reverse(head, left, right);
}

private ListNode reverse(ListNode head, int left, int right) {
    if (left == 1) {
        return LeetCode92$.reverseLink(head, right);
    }
    head.next = reverse(head.next, left - 1, right - 1);
    return head;
}

推荐关注公众号，建立自己的Android知识体系。

开源库推荐

最好用的轮播图库：BannerViewPager

ViewPager指示器：ViewPagerIndicator

Contact

欢迎加群交流: QQ群60902509

QQ群 入群加微信
QQ Group WeChat

公众号:玩转安卓Dev

Java基础

面向对象与Java基础知识

Java集合框架

JVM

多线程与并发

设计模式

Kotlin

Android

项目相关问题

Android基础知识

Android消息机制

Android Binder

View事件分发机制

Android屏幕刷新机制

View的绘制流程

Activity启动

Framework

性能优化

Jetpack&系统View

第三方框架实现原理

计算机网络

算法

排序算法

查找相关

链表相关

数组相关

二叉树

字符串

递归

动态规划

Clone this wiki locally