首页 > 其他分享 >【链表5】两个链表的第一个公共结点

【链表5】两个链表的第一个公共结点

时间:2022-11-22 12:31:41浏览次数:43  
标签:结点 ListNode val int 链表 pHead1 pHead2 公共 null


题目描述

输入两个链表,找出它们的第一个公共结点。

如:链表1:1>>>2>>>3>>6>>>7     

链表2: 4>>>5>>6>>>7

最优解:

交叉遍历两个链表,寻找公共节点:

/*
public class ListNode {
int val;
ListNode next = null;

ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
ListNode node1 = pHead1;
ListNode node2 = pHead2;
while(node1 != node2) {
node1 = node1 == null ? pHead2 : node1.next;
node2 = node2 == null ? pHead1 : node2.next;
}
return node2;
}
}

 

 

 

方法一:

  两个链表公共结点为6.如何获取?先让链表走一步(即长链表比短链表多的部分),这时长链表指针在2位置,短链表在4位置。

然后一起走,碰到第一个相等的数(6),即为第一个公共结点。

/*
public class ListNode {
int val;
ListNode next = null;

ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if(pHead1 == null || pHead2 == null)
return null;

ListNode firstCommonNode = null;
int len1 = getLenOfListNode(pHead1);
int len2 = getLenOfListNode(pHead2);

int dif = len1 > len2 ? (len1 - len2) : (len2 - len1);
ListNode fast = len1 > len2 ? pHead1 : pHead2;
ListNode slow = len1 < len2 ? pHead1 : pHead2;

for(int i = 0; i < dif; i++){
fast = fast.next;
}

while(slow != null && fast != null){
if(slow.val == fast.val)
return slow;
slow = slow.next;
fast = fast.next;
}

return null;
}

//获取链表长度
private int getLenOfListNode(ListNode pHead){
if(pHead == null)
return 0;
int len =0 ;
while(pHead != null){
len++;
pHead = pHead.next;
}
return len;
}


}

 

方法二:用HashSet

/*
public class ListNode {
int val;
ListNode next = null;

ListNode(int val) {
this.val = val;
}
}*/
import java.util.*;

public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {

if(pHead1 == null ||pHead2==null)
return null;
Set<ListNode> set = new HashSet<>();
//先加入链表1 中的结点
while(pHead1 != null){
set.add(pHead1);
pHead1 = pHead1.next;
}

//同时加入结点2中的元素,如果set.add(pHead2)为false,则代表此元素为两链表公共结点
while(pHead2 != null && set.add(pHead2)){
pHead2 = pHead2.next;
}
return pHead2;

}
}

 

 

方法三:

/*
public class ListNode {
int val;
ListNode next = null;

ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
private int getLenOfListNode(ListNode pHead){
int count = 0;
while(pHead != null){
count++;
pHead = pHead.next;
}
return count;
}
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if(pHead1 == null || pHead2 == null)
return null;

ListNode firstCommonNode = null;
int len1 = getLenOfListNode(pHead1);
int len2 = getLenOfListNode(pHead2);

int dif = len1 > len2 ? (len1 - len2) : (len2 - len1);
ListNode fast = len1 > len2 ? pHead1 : pHead2;
ListNode slow = len1 < len2 ? pHead1 : pHead2;

for(int i = 0; i < dif; i++){
fast = fast.next;
}

while(slow != null && fast != null){
if(slow.val == fast.val)
return slow;
slow = slow.next;
fast = fast.next;
}

return null;
}
}

 

 

 

 

 

 

 

 

标签:结点,ListNode,val,int,链表,pHead1,pHead2,公共,null
From: https://blog.51cto.com/u_15886477/5877696

相关文章