链表的常见算法总结

1、两个单链表求和

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    //双栈法
    LinkedList<ListNode> stack1 = new LinkedList<>();
    LinkedList<ListNode> stack2 = new LinkedList<>();
    ListNode res = null;
    while (l1 != null) {
        stack1.push(l1);
        l1 = l1.next;
    }
    while (l2 != null) {
        stack2.push(l2);
        l2 = l2.next;
    }
    //进位
    int carry = 0;
    while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
        int sum = 0;
        if (!stack1.isEmpty()) {
            sum += stack1.pop().val;
        }
        if (!stack2.isEmpty()) {
            sum += stack2.pop().val;
        }
        sum += carry;
        //进位
        carry = sum / 10;
        //和取模
        ListNode node = new ListNode(sum % 10);
        node.next = res;
        res = node;
    }
    return res;
}

将两个链表构造两个栈，使用栈先进后出的特性，做两个链表倒叙做计算，注意进位的情况。

2、单链表非递归翻转，不借助其他数据结构

206. 反转链表
单链表的翻转就是将相邻两个节点的指针翻转。需要借助两个额外的指针用来存储当前节点的前后节点。

public static ListNode reverseList(ListNode head) {
    ListNode pre = null;
    while(head!=null){
        ListNode temp = head.next;
        head.next = pre;
        pre = head;
        head = temp;
    }
    return pre;
}

3、回文链表(用 O(n) 时间复杂度和 O(1) 空间复杂度)

234. 回文链表
通过快慢指针获取链表中间节点位置，将后半段链表反转，之后迭代前后链表，判断值是否相同。

public static boolean isPalindrome(ListNode head) {
    //边界检查，如果链表为空，或者只有一个节点，直接返回true
    if (head == null || head.next == null) {
        return true;
    }
    //使用快慢指针获取链表中间节点位置
    ListNode fast = head;
    ListNode slow = head;
    //当有偶数个节点时，fast为null时，到达终点
    //当有奇数个节点时，fast.next为null，到达终点
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    //到达终点时，奇数个节点，slow正好处于中间位置，偶数个节点时slow处于后半段的开始位置。
    //slow作为前半段链表起点，fast作为后半段链表起点
    fast = slow;
    slow = head;
    //反转fast开头的后半段链表
    ListNode pre = null;
    while (fast != null) {
        ListNode temp = fast.next;
        fast.next = pre;
        pre = fast;
        fast = temp;
    }
    //迭代slow与pre，比较每个值
    while (slow != null && pre != null) {
        if(slow.val!=pre.val){
            return false;
        }
        slow = slow.next;
        pre = pre.next;
    }
    return true;
}

4、环形链表

141. 环形链表
检测链表中是否有环，可以使用两种方法：使用HashSet或者快慢指针。

public static boolean hasCycle(ListNode head) {
    //边界检查,如果链表为空或者只有一个节点，直接返回false
    if (head == null || head.next == null) {
        return false;
    }
    //使用快慢指针
    ListNode fast = head.next;
    ListNode slow = head;
    //快慢指针没有重合就一直循环
    while (fast != slow) {
        //只要快指针到达链表尾部，则无环
        if (fast == null || fast.next == null) {
            return false;
        }
        fast = fast.next.next;
        slow = slow.next;
    }
    return true;
}

5、删除链表种所有值为val的节点

203. 移除链表元素
链表移除操作要借助一个哨兵节点，简化删除。

public static ListNode removeElements(ListNode head, int val) {
    //使用哨兵节点
    ListNode sentinel = new ListNode(0);
    sentinel.next = head;
    ListNode pre = sentinel;
    while (head != null) {
        //如果当前的节点就是要删除的节点
        if (head.val == val) {
            //前一个节点直接指向后一个节点
            pre.next = head.next;
        } else {
            //pre向后移动
            pre = head;
        }
        head = head.next;
    }
    return sentinel.next;
}

6、合并两个有序链表

21. 合并两个有序链表
需要使用哨兵节点。

public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    //定义哨兵节点
    ListNode head = new ListNode(0);
    ListNode pre = head;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            pre.next = l1;
            l1 = l1.next;
        } else {
            pre.next = l2;
            l2 = l2.next;
        }
        pre = pre.next;
    }
    if (l1 == null) {
        pre.next = l2;
    } else {
        pre.next = l1;
    }
    return head.next;
}