已知两个非降序链表序列S1与S2,设计函数构造出S1与S2合并后的新的非降序链表S3。 要求S3中没有重复元素。
时间: 2024-03-16 12:19:33 浏览: 23
可以使用双指针法来合并两个非降序链表S1和S2,同时去除重复元素。具体步骤如下:
1. 初始化两个指针p1和p2分别指向S1和S2的头节点。
2. 新建一个空链表S3。
3. 循环比较p1和p2所指节点的值,将较小值的节点加入S3中,同时将其对应的指针p1或p2向后移动一位。
4. 如果p1和p2所指节点的值相等,则只将其中一个节点加入S3中,同时两个指针都向后移动一位。
5. 当p1或p2到达链表末尾时,将剩余节点加入S3中。
6. 返回S3链表。
下面是Java代码实现:
```java
public ListNode merge(ListNode s1, ListNode s2) {
ListNode p1 = s1, p2 = s2;
ListNode s3 = new ListNode(0); // 新建S3链表
ListNode p3 = s3;
while (p1 != null && p2 != null) {
if (p1.val < p2.val) { // 将较小值的节点加入S3中
p3.next = p1;
p1 = p1.next;
} else if (p1.val > p2.val) {
p3.next = p2;
p2 = p2.next;
} else { // 如果节点值相等,则只将其中一个节点加入S3中
p3.next = p1;
p1 = p1.next;
p2 = p2.next;
}
p3 = p3.next;
}
// 将剩余节点加入S3中
if (p1 != null) {
p3.next = p1;
}
if (p2 != null) {
p3.next = p2;
}
return s3.next;
}
```