【零基础算法】链表算法

 

链表算法

这次带来的是有关于链表题的相应训练，对应的数据结构较为基础，大家可以自行去了解，或者等后面博主有空复习时重新写一篇博客，今天就暂时直接开始算法吧！

这次将围绕以下几个方面来进行链表算法的练习：

1. 合并两个有序链表

2. 链表的分解

3. 合并k个有序链表

4. 寻找单链表的倒数第k个节点

5. 寻找单链表的中点

6. 判断单链表是否包含环并找出环七点

7. 判断两个单链表是否相交并找出交点

这些操作基本上都使用到了双链表的算法

合并两个有序链表

21. 合并两个有序链表 - 力扣（LeetCode）

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode ans = null;
        ListNode tmp = null;
        while(list1!=null || list2!=null) {
            int tmp1 = list1 == null ? 101:list1.val;
            int tmp2 = list2 == null ? 101:list2.val;
            int tmp3;
            if(tmp1 < tmp2) {
                list1 = list1.next;
                tmp3 = tmp1;
            } else {
                list2 = list2.next;
                tmp3 = tmp2;
            }
            ListNode newNode = new ListNode();
            newNode.val = tmp3;
            if(tmp == null) {
                ans = tmp = newNode;
            } else {
                tmp.next = newNode;
                tmp = newNode;
                tmp.next = null;
            }
        }
        return ans;
    }
}

当你需要创造一条新链表的时候，可以使用虚拟头（dummy）结点简化边界情况的处理。

单链表的分解

86. 分隔链表 - 力扣（LeetCode）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode dummy1 = new ListNode(-1),p1=dummy1;
        ListNode dummy2 = new ListNode(-1),p2=dummy2;
​
        ListNode p3 = head;
        while(p3!=null) {
            if(p3.val < x) {
                ListNode newNode = new ListNode(p3.val);
                p1.next = newNode;
                p1 = newNode;
            } else {
                ListNode newNode = new ListNode(p3.val);
                p2.next = newNode;
                p2 = newNode;
            }
            p3 = p3.next;
        }
        p1.next = dummy2.next;
        p2.next = null;
        return dummy1.next;
    }
}

class Solution {
    // public boolean isPalindrome(ListNode head) {
    //     ListNode head2 = new ListNode(head.val);
    //     ListNode p = head.next;
    //     ListNode p2 = head2;
    //     while(p!=null) {
    //         ListNode newNode = new ListNode(p.val);
    //         p2.next = newNode;
    //         p2 = newNode;
    //         p=p.next;
    //     }
    //     head2 = reverse(head2);
    //     while(head2!=null) {
    //         if(head2.val!=head.val) return false;
    //         head = head.next;
    //         head2 = head2.next;
    //     }
    //     return true;
    // }
 
    // public ListNode reverse(ListNode head) {
    //     if(head == null || head.next == null) {
    //         return head;
    //     }
 
    //     ListNode last = reverse(head.next);
 
    //     head.next.next = head;
    //     head.next = null;
        
    //     return last;
    // }
 
    private ListNode left;
 
    public boolean isPalindrome(ListNode head) {
        left = head;
        return trease(head);
    }
 
    public boolean trease(ListNode head){
        if(head == null) return true;
        boolean res = trease(head.next);
        
        res = res && (left.val == head.val);
        left = left.next;
        return res;
    }
}

这里可以把原链表的节点断开，也可以new新节点。

23. 合并 K 个升序链表 - 力扣（LeetCode）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int len = lists.length;
        //System.out.println(len);
        ListNode dummy = new ListNode(-1),p = dummy;
        int[] nums = new int[len];
        int index = 0;
        int min = 0;
​
        while(true) {
            int count = 0;
            min = 100000;
            for(int i = 0 ; i < len ; i++) {
                nums[i] = lists[i] == null ? 100000:lists[i].val;
                if(nums[i] < min) {
                    min = nums[i];
                    index = i;
                }
                if(lists[i] == null) count++;
            }
            if(count == len) break;
            p.next = lists[index];
            p = lists[index];
            ListNode tmp = lists[index].next;
            lists[index].next = null;
            lists[index] = tmp;
        }
        return dummy.next;
    }
​
}

这里的解法使用最原始的暴力解法，多指针的方法，一次取一个最小数，直到最后所有指针全为空。

升级的用法就使用优先队列（二叉堆）这种数据结构。

ListNode mergeKLists(ListNode[] lists) {
    if (lists.length == 0) return null;
    // 虚拟头结点
    ListNode dummy = new ListNode(-1);
    ListNode p = dummy;
    // 优先级队列，最小堆
    PriorityQueue pq = new PriorityQueue<>(
        lists.length, (a, b)->(a.val - b.val));
    // 将 k 个链表的头结点加入最小堆
    for (ListNode head : lists) {
        if (head != null)
            pq.add(head);
    }
​
    while (!pq.isEmpty()) {
        // 获取最小节点，接到结果链表中
        ListNode node = pq.poll();
        p.next = node;
        if (node.next != null) {
            pq.add(node.next);
        }
        // p 指针不断前进
        p = p.next;
    }
    return dummy.next;
}

​

单链表的倒数第k个节点

普通解法：

1. 遍历一遍链表，得出链表的长度n

2. 再遍历一遍链表，并记录长度，到达n-k+1的时候就是结果

这样需要遍历两边链表

双指针：

1. 先用一个指针，走k步。

2. 用另一个指针指向头节点，之后两个指针一起走，第一个指针走到尽头的时候，第二个指针就是倒数第k个位置。

19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode p1 = head;
        ListNode p2 = head;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        for(int i = 0 ; i < n ; i++) {
            p1 = p1.next;
        }
        while(p1!=null) {
            p1=p1.next;
            p2=p2.next;
            pre = pre.next;
        }
        pre.next = p2.next;
        return dummy.next;
​
    }
}

单链表的中点&判断链表是否有环

中点问题&判断链表是否有环可以使用快慢指针法：

一个指针为fast，一个指针为slow，fast一次前进两步，而slow一次前进一步，那么，当fast到末尾的时候，slow就是表的中点。

需要注意的是，如果链表长度为偶数，也就是说中点有两个的时候，我们这个解法返回的节点是靠后的那个节点。

但如果在链表中，有一次slow追上了fast指针，也就是slow == fast的时候，就说明链表有环

876. 链表的中间结点 - 力扣（LeetCode）

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(true) {
            fast = fast.next;
            if(fast == null) break;
            slow = slow.next;
            fast = fast.next;
            if(fast == null) break;
        }
        return slow;
    }
}

142. 环形链表 II - 力扣（LeetCode）

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null) return null;
        ListNode slow = head;
        ListNode fast = head;
        while(true) {
            fast = fast.next;
            if(fast == null) return null;
            slow = slow.next;
            fast = fast.next;
            if(fast == null) return null;
            if(fast == slow) break;
        }
        slow = head;
        while(slow!=fast) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }   
}

寻找环的入口：快慢指针相遇之后，假设慢指针走了k步，那么快指针走了2k步（因为快指针比满指针快1步）。假设相遇点距离环入口m步，那么实际上满指针走了k-m步（环外），m步（环内）。而快指针了2k步，和慢指针一样，k-m步时环外的，剩下的k+m步是在环内走的，但是环内肯定是有循环的，那么在m处相遇的情况下，快指针入环走m步后，循环了一圈又到m与慢指针相遇，k+m-m=k。所以也就是说，快指针在环内从m处的地方走了k步，又与慢指针相遇。那扣去一开始的相遇点的m步，剩下走k-m就是入口了。所以当快慢指针相遇时，一个指针从头开始走，快指针一次走一步，两个指针相遇时就是入口。

两个链表是否相交

如果用两个指针 p1 和 p2 分别在两条链表上前进，并不能同时走到公共节点，也就无法得到相交节点 c1。

解决这个问题的关键是，通过某些方式，让 p1 和 p2 能够同时到达相交节点 c1。

可以相当于遍历两个链表，让两个链表变成相同长度。可以让 p1 遍历完链表 A 之后开始遍历链表 B，让 p2 遍历完链表 B 之后开始遍历链表 A，这样相当于「逻辑上」两条链表接在了一起。

如果这样进行拼接，就可以让 p1 和 p2 同时进入公共部分，也就是同时到达相交节点 c1：

160. 相交链表 - 力扣（LeetCode）

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p1 = headA,p2 = headB;
        while(p1 != p2) {
            if(p1 == null) p1 = headB;
            else p1 = p1.next;
            if(p2 == null) p2 = headA;
            else p2 = p2.next;
        }
        return p1;
    }
}

反转单链表

递归实现

递归反转整个链表

对于递归算法，最重要的就是明确递归函数的定义。

以反转单链表代码为例：

// 定义：输入一个单链表头结点，将该链表反转，返回新的头结点
ListNode reverse(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode last = reverse(head.next);
    head.next.next = head;
    head.next = null;
    return last;
}

具体来说，我们的 reverse 函数定义是这样的：

输入一个节点 head，将「以 head 为起点」的链表反转，并返回反转之后的头结点。

所以，递归第一次后，除了第一个位置，其他地方的节点已经被反转，并返回了反转后的头节点。 但这时还没有对整个链表的结构进行处理，也就是说，第二个节点的next = null ，而头节点的next 是第二个节点，那么接下来就是将第二个节点的next指向第一个节点。而第一个节点的next = null。

递归反转链表前N个节点

ListNode successor = null; // 后驱节点
​
// 反转以 head 为起点的 n 个节点，返回新的头结点
ListNode reverseN(ListNode head, int n) {
    if (n == 1) {
        // 记录第 n + 1 个节点
        successor = head.next;
        return head;
    }
    // 以 head.next 为起点，需要反转前 n - 1 个节点
    ListNode last = reverseN(head.next, n - 1);
​
    head.next.next = head;
    // 让反转之后的 head 节点和后面的节点连起来
    head.next = successor;
    return last;
}

具体的区别：

1、base case 变为 n == 1，反转一个元素，就是它本身，同时要记录后驱节点。

2、刚才我们直接把 head.next 设置为 null，因为整个链表反转后原来的 head 变成了整个链表的最后一个节点。但现在 head 节点在递归反转之后不一定是最后一个节点了，所以要记录后驱 successor（第 n + 1 个节点），反转之后将 head 连接上。

反转链表的一部分

给一个索引区间 [m, n]（索引从 1 开始），仅仅反转区间中的链表元素

首先，如果 m == 1，就相当于反转链表开头的 n 个元素嘛，也就是反转前N个数的功能。

如果m！=1，把下一个节点视为1的话，就是反转下一个节点后的n个节点，但由于整个链表去掉了1个节点，所以整个链表的总节点数实际上也要比原先的个数少1个。例如：原先如果是从2下标到5下标反转，而总数组有1，6的下标。那么实际上一开始后发现m不满足时，2下标变为1的时候，需要反转的地方就变成1，到4了，也就是都会少一。

ListNode reverseBetween(ListNode head, int m, int n) {
    // base case
    if (m == 1) {
        return reverseN(head, n);
    }
    // 前进到反转的起点触发 base case
    head.next = reverseBetween(head.next, m - 1, n - 1);
    return head;
}

迭代实现

25. K 个一组翻转链表 - 力扣（LeetCode）

class Solution {
    
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head == null) return null;
​
        ListNode start, end;
        start = end = head;
​
        for(int i = 0 ; i < k ; i++) {
            if(end == null) return head;
            end = end.next;
        }
​
        ListNode newhead = reverseK(start,end);
​
        start.next = reverseKGroup(end , k );
​
        return newhead;
    } 
​
    public ListNode reverseK(ListNode head,ListNode end) {
        ListNode pre = null;
        ListNode now = head;
        ListNode next = head;
        while(now != end) {
            next = now.next;
            now.next = pre;
            pre = now;
            now = next;
        }
        return pre;
    }
}

实际上也用到了递归的思想，将整个链表看作一个大问题的话，实际上就是每次都要反转前k个节点，直到节点树目不足k个。那么第一次反转k个之后，剩下的就是原链表树目-k个节点的链表，是一个更小的问题，而原先反转完之后，我们希望函数返回的是反转完的头结点，所以，实际中上一次反转的末尾的下一个对应的就是下一次反转函数返回的头结点。

判断回文链表

寻找回文串的核心思想是从中心向两端扩展

// 在 s 中寻找以 s[left] 和 s[right] 为中心的最长回文串
String palindrome(String s, int left, int right) {
    // 防止索引越界
    while (left >= 0 && right < s.length()
            && s.charAt(left) == s.charAt(right)) {
        // 双指针，向两边展开
        left--;
        right++;
    }
    // 返回以 s[left] 和 s[right] 为中心的最长回文串
    return s.substring(left + 1, right);
}

因为回文串长度可能为奇数也可能是偶数，长度为奇数时只存在一个中心点，而长度为偶数时存在两个中心点，所以上面这个函数需要传入 l 和 r。

判断是不是回文串

boolean isPalindrome(String s) {
    // 一左一右两个指针相向而行
    int left = 0, right = s.length() - 1;
    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

接下来，判断一个单链表是不是回文链表

这道题的关键在于，单链表无法倒着遍历，无法使用双指针技巧。

可以思考递归遍历的方法，递归返回时，如果是在返回前，就是顺序遍历，如果是在返回后写就是后序遍历。

而后序遍历的话，就可以在返回时与前半部分的节点进行比较，就可以知道是不是回文串了。

234. 回文链表 - 力扣（LeetCode）

    private ListNode left;
​
    public boolean isPalindrome(ListNode head) {
        left = head;
        return trease(head);
    }
​
    public boolean trease(ListNode head){
        if(head == null) return true;
        boolean res = trease(head.next);
        
        res = res && (left.val == head.val);
        left = left.next;
        return res;
    }

这题当然也可以反转链表之后再判断：

class Solution {
     public boolean isPalindrome(ListNode head) {
         ListNode head2 = new ListNode(head.val);
         ListNode p = head.next;
         ListNode p2 = head2;
         while(p!=null) {
             ListNode newNode = new ListNode(p.val);
             p2.next = newNode;
             p2 = newNode;
             p=p.next;
         }
         head2 = reverse(head2);
         while(head2!=null) {
             if(head2.val!=head.val) return false;
             head = head.next;
             head2 = head2.next;
         }
         return true;
     }
 
     public ListNode reverse(ListNode head) {
         if(head == null || head.next == null) {
             return head;
         }
 
         ListNode last = reverse(head.next);
 
         head.next.next = head;
         head.next = null;
        
         return last;
     }
 
}

        本文仅作为博主学习过程的记录。建议双指针，虚拟节点的使用以及对于链表递归的写法深入了解。