找出两个链表相交的结点(定义链表结构)_

牛客883929号

//节点定义

typedef struct Node{

int data;

Node* next;

}

//寻找内存位置相同的节点

Node* Search(Node* head1,Node* head2){

if(head1==null || head2==null)

return null;

int diff = head1.size() - head2.size();

Node* p1=head1,p2=head2;

if(diff<0){

for(int i=1;i<=diff;i++)

p2 = p2->next;

}else if(diff>0){

for(int i=1;i<=diff;i++)

p1 = p1->next;

}

while(p1->next!=p2->next){

p1 = p1->next;

p2 = p2->next;

}

return p1->next;

}

发表于 2016-05-10 21:13:45 回复(0)

啦啦啦201809042342197

class Node {

  Node next;
   int val;
   public Node(int val) {
       this.val = val;
   }

}

Class solution {

public void

}

发表于 2019-03-14 16:36:39 回复(0)

牛客79631828号

//本题可以分成三个问题：

//如何判断一个链表是否有环，有则返回第一个入还节点，无则null

//如何判断两个无环链表是否相交，相交则返回第一个相交节点，不相交则返回null

//如何判断两个有环链表是否相交，相交则.....

//一个无环和一个有环是不可能相交的，因为一旦相交了则两个都必将有环，一个node不可能有两个 //next

public class Node {

public int val;

public Node next;

public Node (int data) {

this.val = data;

}

//判断一个链表是否有环

public Node getLoopNode (Node head) {

//设置快慢指针，快每次走两步，慢每次一步，开始遍历

Node slow = head;

Node fast = head;

while (slow != fast) {

if (fast.next == null || fast.next.next == null)

return null;

fast = fast.next.next;

slow = slow.next;

}

//再次把fast放回头部，且每次开始与slow一样各走一步，则第二次相遇点为第一个入环点

fast = head;

while (fast != slow) {

fast = fast.next;

slow = slow.next;

}

return fast;

}

//判断两个无环链表是否相交

public Node noLoop(Node head1, Node head2) {

if (head1 == null || head2 == null)

return null;

//分别遍历两个链表记录长度差值并查看是否相交

Node cur1 = head1;

Node cur2 = head2;

int steps = 0;

while (cur1.next != null) {

cur1 = cur1.next;

steps++;

}

while (cur2.next != null) {

cur2 = cur.next;

steps--;

}

if (cur1 != cur2)

return null;

cur1 = steps >= 0 ? head1 : head2;

cur2 = cur1 == head1 ? head2 : head1;

n = Math.abs(n);

while(n-- != 0) {

cur1 = cur1.next;

}

while (cur1 != cur2) {

cur1 = cur1.next;

cur2 = cur2.next;

}

return cur1;

}

//判断两个有环链表是否相交

//此种情况分三种：1. 两链表相交点在环上；2. 相交点不在环上；3. 根本不相交

public Node bothLoop(Node head1, Node head2, Node loop1, Node loop2) {

Node cur1 = null;

Node cur2 = null;

//情况1或情况3

if (loop1 != loop2) {

cur1 = loop1.next;

while (cur1 != loop1) {

//情况1, 返回loop1或loop2皆可

if (cur1 == loop2) {

return loop2;

}

cur1 = cur1.next;

}

//情况3

return null;

}

//情况2

else {

cur1 = head1;

cur2 = head2;

int n = 0;

while (cur1 != loop1) {

cur1 = cur1.next;

n++;

}

while (cur2 != loop2) {

n--;

cur2 = cur2.next;

}

cur1 = n >= 0 ? head1 : head2;

cur2 = cur1 == head1 ? head2 : head1;

n = Math.abs(n);

while (n-- != 0) {

cur1 = cur1.next;

}

while (cur1 != cur2) {

cur1 = cur1.next;

cur2 = cur2.next;

}

return cur1;

}

//主function

public Node checkCommonNode (Node head1, Node head2) {

if (head1 == null || head2 == null)

return null;

Node loop1 = getLoopNode(head1);

Node loop2 = getLoopNode(head2);

if (loop1 == null && loop2 == null) {

return noLoop(head1, head2);

}

if (loop1 != null && loop2 != null) {

return bothLoop(head1, head2, loop1, loop2);

}

return null;

}

发表于 2021-06-05 16:42:50 回复(0)

FearIsUnreal

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

ListNode(int val) {
this.val = val;
}
}
import java.lang.Math;
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
int length1 = ListLength(pHead1);
int length2 = ListLength(pHead2);
int absLen = Math.abs(length1 - length2);
if(length1 > length2)
{
while(absLen > 0)
{
pHead1 = pHead1.next;
absLen -= 1;
}
}
else
{
while(absLen > 0)
{
pHead2 = pHead2.next;
absLen -= 1;
}
}
//两个链表长度相同了
while(pHead1 != pHead2)
{
pHead2 = pHead2.next;
pHead1 = pHead1.next;
}
return pHead1;
}

public static int ListLength(ListNode head)
{
int len = 0;
while(head != null)
{
len += 1;
head = head.next;
}
return len;
}
}

发表于 2019-03-23 17:45:07 回复(0)

小虎牙

structNode

{

int data;

structNode *next;

}

class solution

{
public:

structNode* FindCommen(structNode* list1,structNode* list2)

{

if(list1==NULL || list2==NULL)

return NULL;

int len1=list1.size();

int len2=list2.size();

int diff;

if(len1>len2)

{

diff=len1-len2;

for(int i=0;i<diff;i++)

{

list1=list1->next;

}

else

{

diff=len2-len1;

for(int i=0;i<diff;i++ )

{

list2=list2->next;

}

while(list1->data != list2->data)

{

list1=list->next;

list2=list2->next;

}

return list1;

}

发表于 2015-11-22 16:04:58 回复(0)

牛客133342452号

//定义节点

class ListNode{

int data;

Node next;

public Node(int data){

this.data = data；

}

public class Solution{

public ListNode getListnode(ListNode node1, ListNode node2){

int length1 = getLength(node1);

int length2 = getLength(node2);

ListNode head1 = Null;

ListNode head2 = Null;

if (length1 > length2){

head1 = node1;

head2 = node2;

}else{

head1 = node2;

head2 = node1;

}

for (int i = 0; i<length1 - length2; ++i){

head1 = head.next;

}

while ( hea1 != Null && head2 != Null){

if (head1 == head2){

return head1;

}

head1 = head1.next;

head2 = head2.next;

}

public int getLength(ListNode node){

int length = 0;

ListNode head = node;

while(head.next != Null){

length ++;

head = head.next;

}

return length;

}

编辑于 2021-09-03 19:10:35 回复(0)

HappingNewBoy

java实现：LeetCode题目160.相交链表

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

ListNode l1 = headA;

ListNode l2 = headB;

while(l1 != l2){

l1 = l1 == null ? headB : l1.next;

l2 = l2 == null ? headA : l2.next;

}

return l1;

}

发表于 2021-04-09 15:51:43 回复(0)

开发者小杨

public class ListNode{
    int value;
    ListNode next;
    ListNode(int x){
        value = x;
        next = null;
    }
}

public class Solution{
    public ListNode getIntersectionNode(ListNode headA, ListNode headB){
        ListNode l1 = headA, l2 = headB;
        while(l1 != l2){
            l1 = (l1 == null)? headB : l1.next;
            l2 = (l2 == null)? headA : l2.next;
        }
        return l1;
    }
}

发表于 2021-02-17 23:37:45 回复(0)

往事如烟613

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *hA = headA;
        ListNode *hB = headB;
        if (!hA || !hB){
            return NULL;
        }
        while (hA && hB && hA!=hB){
            hA = hA -> next;
            hB = hB -> next;
            if (hA == hB){
                break;
            }
            if(!hA){
                hA = headB;
            }
            if(!hB){
                hB = headA;
            }
        }
        return hA;
    }
};

参考：https://www.cnblogs.com/zhanzq/p/10563156.html

发表于 2019-09-25 14:20:25 回复(0)

D206

发表于 2019-08-03 15:47:13 回复(0)

找出两个链表相交的结点(定义链表结构)

问题信息

热门推荐

相关试题