设s和t是表示成单链表的两个串，试编写一个找出s中第1个不在t中出现的字符（假定每个结点只存放1个字符）的算法。 java实现 不用哈希表存储

为了在 Java 中找到两个单链表 s 和 t 中第一个不在对方链表中的字符，你可以遍历两个链表，并使用两个指针同时前进。当遍历到某个字符时，如果它在另一个链表中不存在，就返回这个字符。以下是算法步骤：

1. 定义两个指针 `p1` 和 `p2` 分别指向链表 `s` 和 `t` 的头节点。
2. 使用 while 循环，只要有一个指针不为空：
a. 检查当前指针 `p1` 或 `p2` 所对应的字符，记作 `c1` 和 `c2`。
b. 如果 `c1` 未在另一个链表中出现（即 `c2 == null`），则返回 `c1`。
c. 否则，在各自的链表上移动相应的指针，例如 `p1 = p1.next` 和 `p2 = p2.next`。
3. 如果遍历完都没有找到不同的字符，则说明两个链表完全一致，此时可以假设 `t` 中的最后一个字符是第一个不在 `s` 中的字符，返回 `t` 的最后一个元素。

这里是一个简单的 Java 实现示例：

public class ListNode {
    char val;
    ListNode next;

    ListNode(char val) {
        this.val = val;
        this.next = null;
    }
}

public class Main {
    public static char findFirstDifference(ListNode s, ListNode t) {
        ListNode p1 = s, p2 = t;
        while (p1 != null && p2 != null) {
            if (p1.val != p2.val) {
                return p1.val;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        // 如果 s 长于 t 或者 s 中有 t 不存在的字符，返回 s 的下一个字符
        return p1 != null ? p1.val : p2.val;
    }

    public static void main(String[] args) {
        // 测试代码
        ListNode s = new ListNode('a');
        s.next = new ListNode('b');
        s.next.next = new ListNode('c');
        s.next.next.next = new ListNode('d');

        ListNode t = new ListNode('a');
        t.next = new ListNode('b');
        t.next.next = new ListNode('c');

        System.out.println(findFirstDifference(s, t));  // 输出 'd'
    }
}