[编程题]打印两个升序链表的公共部分
要始终牢记两个链表都是升序的。从头开始遍历两个链表，每次移动值小的指针（因为大的要等小的追上来才有相等的可能），相等的时候就打印节点的值，并同时移动两个链表的指针，直到某个链表的遍历结束。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
class ListNode {
public int val;
public ListNode next;
public ListNode(int val) {
this.val = val;
this.next = null;
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int m = Integer.parseInt(br.readLine());
String[] strList1 = br.readLine().trim().split(" ");
int n = Integer.parseInt(br.readLine());
String[] strList2 = br.readLine().trim().split(" ");
ListNode head1 = new ListNode(Integer.parseInt(strList1[0]));
ListNode cur1 = head1;
for(int i = 1; i < m; i++){
cur1.next = new ListNode(Integer.parseInt(strList1[i]));
cur1 = cur1.next;
}
ListNode head2 = new ListNode(Integer.parseInt(strList2[0]));
ListNode cur2 = head2;
for(int i = 1; i < n; i++){
cur2.next = new ListNode(Integer.parseInt(strList2[i]));
cur2 = cur2.next;
}
while(head1 != null && head2 != null){
if(head1.val < head2.val){
head1 = head1.next;
}else if(head1.val > head2.val){
head2 = head2.next;
}else{
System.out.print(head1.val + " ");
head1 = head1.next;
head2 = head2.next;
}
}
}
}
发表于 2021-06-06 19:49:58
回复(0)
这个题很简单，从头开始遍历两个链表，移动大的那个链表的头指针，如果相等则打印，一直到
某个链表遍历结束
#include<iostream>
using namespace std;
struct ListNode
{
ListNode* next;
int val;
ListNode(int val)
: next(nullptr),val(val){}
};
int main()
{
long long n,m;
cin >> n;
ListNode L1(-1);
ListNode* tmp = &L1;
for(int i = 0;i<n;i++)
{
int x;
cin >> x;
ListNode* newnode = new ListNode(x);
tmp->next = newnode;
tmp = newnode;
}
ListNode L2(-1);
tmp = &L2;
cin >> m;
for(int i = 0;i<m;i++)
{
int x;
cin >> x;
ListNode* newnode = new ListNode(x);
tmp->next = newnode;
tmp = newnode;
}
ListNode* head1 = L1.next;
ListNode* head2 = L2.next;
while(head1!=nullptr && head2!=nullptr)
{
if(head1->val <head2->val)
head1 = head1->next;
else if(head1->val > head2->val)
head2 = head2->next;
else
{
cout << head1->val << " ";
head1 = head1->next;
head2 = head2->next;
}
}
cout << endl;
}
发表于 2019-08-19 10:58:21
回复(0)
import java.util.Scanner;
/**
* 思路：
* 这道题有一个很关键的部分在于【两个升序链表】
* 那么大致思路就是，各自用一个指针指向链表，当a指针元素>b指针元素，则b指针继续往前移动，找到=a or >a的元素
* 如果是>a，那么就轮到a指针跟上来了，直到找到相等的为止
*
*/
class Node {
public Node next;
public int val;
Node(int val) {
this.val = val;
}
/**
* 数组转链表
* return 头结点
*/
public static Node trans(String[] nums) {
Node head = new Node(Integer.parseInt(nums[0]));
Node cur = head;
for(int i = 1; i < nums.length; i++) {
cur.next = new Node(Integer.parseInt(nums[i]));
cur = cur.next;
}
return head;
}
/**
* 打印公共部分
*/
public static void printComment(Node head1, Node head2) {
// 用于保存要打印的值
StringBuilder builder = new StringBuilder();
// 退出条件：当builder不为空，而再次产生新冲突时，或任意链表被遍历完
while (head1 != null && head2 != null) {
if (head1.val == head2.val) {
builder.append(head1.val).append(" ");
head1 = head1.next;
head2 = head2.next;
} else if (head1.val < head2.val) {
head1 = head1.next;
} else {
head2 = head2.next;
}
}
System.out.println(builder.substring(0, builder.length()-1));
}
}
public class Main {
/**
* 4
* 1 2 3 4
* 5
* 1 2 3 5 6
*/
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 读数字似乎没什么意义
in.nextLine();
String[] nums = in.nextLine().split(" ");
Node head1 = Node.trans(nums);
in.nextLine();
nums = in.nextLine().split(" ");
Node head2 = Node.trans(nums);
Node.printComment(head1, head2);
}
}
/**
* 思路：
* 这道题有一个很关键的部分在于【两个升序链表】
* 那么大致思路就是，各自用一个指针指向链表，当a指针元素>b指针元素，则b指针继续往前移动，找到=a or >a的元素
* 如果是>a，那么就轮到a指针跟上来了，直到找到相等的为止
*
*/
class Node {
public Node next;
public int val;
Node(int val) {
this.val = val;
}
/**
* 数组转链表
* return 头结点
*/
public static Node trans(String[] nums) {
Node head = new Node(Integer.parseInt(nums[0]));
Node cur = head;
for(int i = 1; i < nums.length; i++) {
cur.next = new Node(Integer.parseInt(nums[i]));
cur = cur.next;
}
return head;
}
/**
* 打印公共部分
*/
public static void printComment(Node head1, Node head2) {
// 用于保存要打印的值
StringBuilder builder = new StringBuilder();
// 退出条件：当builder不为空，而再次产生新冲突时，或任意链表被遍历完
while (head1 != null && head2 != null) {
if (head1.val == head2.val) {
builder.append(head1.val).append(" ");
head1 = head1.next;
head2 = head2.next;
} else if (head1.val < head2.val) {
head1 = head1.next;
} else {
head2 = head2.next;
}
}
System.out.println(builder.substring(0, builder.length()-1));
}
}
public class Main {
/**
* 4
* 1 2 3 4
* 5
* 1 2 3 5 6
*/
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 读数字似乎没什么意义
in.nextLine();
String[] nums = in.nextLine().split(" ");
Node head1 = Node.trans(nums);
in.nextLine();
nums = in.nextLine().split(" ");
Node head2 = Node.trans(nums);
Node.printComment(head1, head2);
}
}
发表于 2020-08-26 17:51:07
回复(0)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static class Node {
public int value;
public Node next;
public Node(int value) {
this.value = value;
}
}
public static void printCommonPart(Node head1, Node head2) {
if (head1 == null || head2 == null) {
return;
}
while (head1 != null && head2 != null) {
if (head1.value > head2.value) {
head2 = head2.next;
} else if (head1.value < head2.value) {
head1 = head1.next;
} else {
System.out.print(head1.value + " ");
head1 = head1.next;
head2 = head2.next;
}
}
System.out.println();
}
private static Node listGenerator(int length, String[] numbers) {
Node head = new Node(Integer.parseInt(numbers[0]));
Node cur = head;
for (int i = 1; i < length; i++) {
cur.next = new Node(Integer.parseInt(numbers[i]));
cur = cur.next;
}
cur.next = null;
return head;
}
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(bufferedReader.readLine());
String[] numbers1 = bufferedReader.readLine().split(" ");
int m = Integer.parseInt(bufferedReader.readLine());
String[] numbers2 = bufferedReader.readLine().split(" ");
Node head1 = listGenerator(n, numbers1);
Node head2 = listGenerator(m, numbers2);
printCommonPart(head1, head2);
}
}
发表于 2019-12-22 14:57:52
回复(0)
# include <bits/stdc++.h>
using namespace std;
struct list_node{
int val;
struct list_node * next;
}; //链表的节点
list_node * input_list(void) //读入链表
{
int n, val;
list_node * phead = new list_node();
list_node * cur_pnode = phead;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &val);
if (i == 1) {
cur_pnode->val = val;
cur_pnode->next = NULL;
}
else {
list_node * new_pnode = new list_node();
new_pnode->val = val;
new_pnode->next = NULL;
cur_pnode->next = new_pnode;
cur_pnode = new_pnode;
}
}
return phead;
}
void sol(list_node * a_head, list_node * b_head)
{
while(a_head && b_head){
if(a_head->val == b_head->val){
cout<<a_head->val<<" ";
a_head = a_head->next;
b_head = b_head->next;
}else if(a_head->val > b_head->val)
b_head = b_head->next;
else
a_head = a_head->next;
}
}
int main ()
{
list_node * a_head = input_list(); // A 链表的头节点
list_node * b_head = input_list(); // B 链表的头节点
sol(a_head, b_head);
return 0;
}
发表于 2020-03-14 02:04:33
回复(0)
# include <bits/stdc++.h>
using namespace std;
struct list_node{
int val;
struct list_node * next;
}; //链表的节点
list_node * input_list(void) //读入链表
{
int n, val;
list_node * phead = new list_node();
list_node * cur_pnode = phead;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &val);
if (i == 1) {
cur_pnode->val = val;
cur_pnode->next = NULL;
}
else {
list_node * new_pnode = new list_node();
new_pnode->val = val;
new_pnode->next = NULL;
cur_pnode->next = new_pnode;
cur_pnode = new_pnode;
}
}
return phead;
}
void sol(list_node * a_head, list_node * b_head)
{
//////在下面完成代码
while (a_head && b_head)
{
if (a_head->val == b_head->val)
{
cout << a_head->val << " ";
a_head = a_head->next;
b_head = b_head->next;
}
else if (a_head->val < b_head->val) a_head = a_head->next;
else b_head = b_head->next;
}
}
int main ()
{
list_node * a_head = input_list(); // A 链表的头节点
list_node * b_head = input_list(); // B 链表的头节点
sol(a_head, b_head);
return 0;
}
发表于 2019-10-12 19:37:31
回复(0)
# include <bits/stdc++.h>
using namespace std;
struct list_node{
int val;
struct list_node * next;
}; //链表的节点
list_node * input_list(void) //读入链表
{
int n, val;
list_node * phead = new list_node();
list_node * cur_pnode = phead;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &val);
if (i == 1) {
cur_pnode->val = val;
cur_pnode->next = NULL;
}
else {
list_node * new_pnode = new list_node();
new_pnode->val = val;
new_pnode->next = NULL;
cur_pnode->next = new_pnode;
cur_pnode = new_pnode;
}
}
return phead;
}
void sol(list_node * a_head, list_node * b_head)
{
//////在下面完成代码
while(a_head&&b_head)
{
int a=a_head->val,b=b_head->val;
if(a==b)
{
cout<<a<<" ";
a_head=a_head->next;
b_head=b_head->next;
}
else if(a>b)
b_head=b_head->next;
else
a_head=a_head->next;
}
}
int main ()
{
list_node * a_head = input_list(); // A 链表的头节点
list_node * b_head = input_list(); // B 链表的头节点
sol(a_head, b_head);
return 0;
}
发表于 2019-09-01 18:48:52
回复(0)
void sol(list_node * a_head, list_node * b_head)
{
//////在下面完成代码
list_node * p1 = a_head;
list_node * p2 = b_head;
while(p1 && p2){
if(p1->val == p2->val){
cout << p1->val << " ";
p1 = p1->next;
p2 = p2->next;
}
else if(p1->val < p2->val){
p1 = p1->next;
if(p1 == nullptr)
return;
}
else{
p2 = p2->next;
if(p2 == nullptr)
return;
}
}
}
发表于 2019-08-02 18:54:19
回复(0)
n = int(input())
ls1 = list(map(int,input().split()))
m = int(input())
ls2 = list(map(int,input().split()))
i,j = 0,0
ls = []
while i < n and j < m:
if ls1[i] == ls2[j]:
ls.append(ls1[i])
i += 1
j += 1
else:
if ls1[i] < ls2[j]:
i += 1
else:
j += 1
ls.sort()
print(' '.join(map(str,ls)))
发表于 2021-09-07 09:12:15
回复(0)
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine().trim());
String[] rawInput = br.readLine().trim().split(" ");
Node firstList = getInputLinkedList(rawInput, n);
int m = Integer.parseInt(br.readLine().trim());
rawInput = br.readLine().trim().split(" ");
Node secondList = getInputLinkedList(rawInput, m);
String res = getListCommon(firstList, secondList);
System.out.print(res);
br.close();
}
private static Node getInputLinkedList(String[] rawInput, int length) {
Node head = null, curNode = null;
for (int i = 0; i < length; i++) {
Node tmp = new Node(Integer.parseInt(rawInput[i]));;
if (null == head) {
head = tmp;
} else {
curNode.next = tmp;
}
curNode = tmp;
}
return head;
}
private static String getListCommon(Node first, Node second) {
StringBuilder sb = new StringBuilder();
while (null != first && null != second) {
if (first.value == second.value) {
sb . append(first.value) . append(" ");
first = first.next;
second = second.next;
} else if (first.value > second.value) {
second = second.next;
} else {
first = first.next;
}
}
return sb.toString().trim();
}
}
class Node {
public int value;
public Node next;
public Node(int value) {
this.value = value;
next = null;
}
}
发表于 2020-07-16 00:07:03
回复(0)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int[] nums1 = new int[n];
for (int i = 0; i < n; i++) {
nums1[i] = scan.nextInt();
}
int m = scan.nextInt();
int[] nums2 = new int[m];
for (int i = 0; i < m; i++) {
nums2[i] = scan.nextInt();
}
int index1 = 0, index2 = 0;
while (index1 < n && index2 < m) {
if (nums1[index1] == nums2[index2]) {
System.out.print(nums1[index1] + " ");
index1++;
index2++;
} else if (nums1[index1] < nums2[index2]) {
index1++;
} else {
index2++;
}
}
}
}
发表于 2020-07-05 06:00:10
回复(0)
void addlist(List L1,List L2)
{
if(L1->Next != NULL){
L1 = L1->Next;
}
if(L2->Next != NULL){
L2 = L2->Next;
}
while(L1->Next != NULL && L2->Next != NULL){
if(L1->Data > L2->Data){
L2 = L2->Next;
}
else if(L2->Data > L1->Data){
L1 = L1->Next;
}
else if(L2->Data == L1->Data){
printf("%d ",L1->Data);
L1 = L1->Next;
L2 = L2->Next;
}
}
if(L1->Next == NULL && L2->Next == NULL){
if(L2->Data == L1->Data){
printf("%d ",L1->Data);
}
}
while(L1->Next != NULL){
if(L1->Data>L2->Data){
break;
}
else if(L2->Data>L1->Data){
L1 = L1->Next;
}
else if(L2->Data==L1->Data){
printf("%d ",L1->Data);
break;
}
}
while(L2->Next != NULL){
if(L2->Data>L1->Data){
break;
}
else if(L1->Data>L2->Data){
L2 = L2->Next;
}
else if(L2->Data==L1->Data){
printf("%d ",L1->Data);
break;
}
}
}
{
if(L1->Next != NULL){
L1 = L1->Next;
}
if(L2->Next != NULL){
L2 = L2->Next;
}
while(L1->Next != NULL && L2->Next != NULL){
if(L1->Data > L2->Data){
L2 = L2->Next;
}
else if(L2->Data > L1->Data){
L1 = L1->Next;
}
else if(L2->Data == L1->Data){
printf("%d ",L1->Data);
L1 = L1->Next;
L2 = L2->Next;
}
}
if(L1->Next == NULL && L2->Next == NULL){
if(L2->Data == L1->Data){
printf("%d ",L1->Data);
}
}
while(L1->Next != NULL){
if(L1->Data>L2->Data){
break;
}
else if(L2->Data>L1->Data){
L1 = L1->Next;
}
else if(L2->Data==L1->Data){
printf("%d ",L1->Data);
break;
}
}
while(L2->Next != NULL){
if(L2->Data>L1->Data){
break;
}
else if(L1->Data>L2->Data){
L2 = L2->Next;
}
else if(L2->Data==L1->Data){
printf("%d ",L1->Data);
break;
}
}
}
发表于 2019-12-10 15:00:31
回复(0)
class listNode:
def __init__(self,x):
self.value=x
self.next=None
def list2linkList(arr):
if len(arr)==0:
return None
l=1;head=listNode(arr[0])
pre=head
while l<=len(arr):
pre.next=listNode(arr[l-1])
pre=pre.next
l+=1
return head.next
def printSame(head1,head2):
if head1==None&nbs***bsp;head2==None:
return
cur1=head1;cur2=head2
while cur1 and cur2:
if int(cur1.value)<int(cur2.value):
cur1=cur1.next
elif int(cur1.value)>int(cur2.value):
cur2=cur2.next
else:
print(cur1.value),
cur1=cur1.next
cur2=cur2.next
return
n1=int(input())
arr1=raw_input().split(' ')
n2=int(input())
arr2=raw_input().split(' ')
printSame(list2linkList(arr1),list2linkList(arr2)) python 超出内存，75%
发表于 2019-12-02 17:15:50
回复(0)
问题信息
通过挑战的用户
查看代码-
2023-03-12 23:46:46
-
2023-03-10 20:27:48
-
2023-03-10 13:19:01
-
2023-03-09 16:22:31
-
2023-03-07 16:06:11
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
