链表前后缀

[题目链接](https://www.nowcoder.com/practice/96dda1af250d4ad5885c816b9f915c7c)

思路

两个链表共享公共前缀和公共后缀，中间各自有一段不同的部分。我们需要提取公共前缀和公共后缀，拼接后返回。

具体做法

转数组：将两个链表分别转为数组 $A$ 和 $B$ ，长度分别为 $n$ 和 $m$ 。
找公共前缀：从头开始逐个比较，直到 $A[i] \neq B[i]$ 为止，得到公共前缀长度 $\text{pre}$ 。
找公共后缀：从尾部开始逐个比较，直到 $A[n-1-j] \neq B[m-1-j]$ 为止，注意后缀的搜索范围不能与前缀重叠（即最多到 $n - \text{pre}$ 和 $m - \text{pre}$ ），得到公共后缀长度 $\text{suf}$ 。
构造结果：将 $A[0..\text{pre}-1]$ （前缀部分）和 $A[n-\text{suf}..n-1]$ （后缀部分）依次串成新链表返回。

样例演示

以 $A = \{1,2,2,3,4\}$ ， $B = \{1,2,1,2,3,3,4\}$ 为例：

公共前缀： $A[0]=B[0]=1$ ， $A[1]=B[1]=2$ ， $A[2]=2 \neq B[2]=1$ ，所以 $\text{pre} = 2$ 。
公共后缀： $A[4]=B[6]=4$ ， $A[3]=B[5]=3$ ， $A[2]=2 \neq B[4]=3$ ，所以 $\text{suf} = 2$ 。
结果：前缀 $\{1, 2\}$ + 后缀 $\{3, 4\}$ = $\{1, 2, 3, 4\}$ 。

复杂度

时间复杂度： $O(n + m)$ ，遍历两个链表各一次，前缀和后缀比较合计也是 $O(\min(n, m))$ 。
空间复杂度： $O(n + m)$ ，存储两个数组。

代码

C++
Java
Python3
JavaScript

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    ListNode* mergeList(ListNode* a, ListNode* b) {
        vector<int> va, vb;
        for (ListNode* p = a; p; p = p->next) va.push_back(p->val);
        for (ListNode* p = b; p; p = p->next) vb.push_back(p->val);

        int n = va.size(), m = vb.size();

        // 找公共前缀长度
        int pre = 0;
        while (pre < n && pre < m && va[pre] == vb[pre]) pre++;

        // 找公共后缀长度
        int suf = 0;
        while (suf < n - pre && suf < m - pre && va[n - 1 - suf] == vb[m - 1 - suf]) suf++;

        // 构造结果：前缀 + 后缀
        ListNode dummy(0);
        ListNode* cur = &dummy;
        for (int i = 0; i < pre; i++) {
            cur->next = new ListNode(va[i]);
            cur = cur->next;
        }
        for (int i = n - suf; i < n; i++) {
            cur->next = new ListNode(va[i]);
            cur = cur->next;
        }
        return dummy.next;
    }
};

import java.util.*;

public class Solution {
    public ListNode mergeList(ListNode a, ListNode b) {
        List<Integer> va = new ArrayList<>();
        List<Integer> vb = new ArrayList<>();
        for (ListNode p = a; p != null; p = p.next) va.add(p.val);
        for (ListNode p = b; p != null; p = p.next) vb.add(p.val);

        int n = va.size(), m = vb.size();

        // 找公共前缀长度
        int pre = 0;
        while (pre < n && pre < m && va.get(pre).equals(vb.get(pre))) pre++;

        // 找公共后缀长度
        int suf = 0;
        while (suf < n - pre && suf < m - pre && va.get(n - 1 - suf).equals(vb.get(m - 1 - suf))) suf++;

        // 构造结果：前缀 + 后缀
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        for (int i = 0; i < pre; i++) {
            cur.next = new ListNode(va.get(i));
            cur = cur.next;
        }
        for (int i = n - suf; i < n; i++) {
            cur.next = new ListNode(va.get(i));
            cur = cur.next;
        }
        return dummy.next;
    }
}

class Solution:
    def mergeList(self, a, b):
        va, vb = [], []
        p = a
        while p:
            va.append(p.val)
            p = p.next
        p = b
        while p:
            vb.append(p.val)
            p = p.next

        n, m = len(va), len(vb)

        # 找公共前缀长度
        pre = 0
        while pre < n and pre < m and va[pre] == vb[pre]:
            pre += 1

        # 找公共后缀长度
        suf = 0
        while suf < n - pre and suf < m - pre and va[n - 1 - suf] == vb[m - 1 - suf]:
            suf += 1

        # 构造结果：前缀 + 后缀
        dummy = ListNode(0)
        cur = dummy
        for i in range(pre):
            cur.next = ListNode(va[i])
            cur = cur.next
        for i in range(n - suf, n):
            cur.next = ListNode(va[i])
            cur = cur.next
        return dummy.next

function mergeList(a, b) {
    const va = [], vb = [];
    for (let p = a; p; p = p.next) va.push(p.val);
    for (let p = b; p; p = p.next) vb.push(p.val);

    const n = va.length, m = vb.length;

    // 找公共前缀长度
    let pre = 0;
    while (pre < n && pre < m && va[pre] === vb[pre]) pre++;

    // 找公共后缀长度
    let suf = 0;
    while (suf < n - pre && suf < m - pre && va[n - 1 - suf] === vb[m - 1 - suf]) suf++;

    // 构造结果：前缀 + 后缀
    const dummy = new ListNode(0);
    let cur = dummy;
    for (let i = 0; i < pre; i++) {
        cur.next = new ListNode(va[i]);
        cur = cur.next;
    }
    for (let i = n - suf; i < n; i++) {
        cur.next = new ListNode(va[i]);
        cur = cur.next;
    }
    return dummy.next;
}