C++ 解决求两个链表的第一个公共结点问题

目录
  • 题目描述：
  • 输入描述：
  • 返回值描述：
  • 示例：
  • 解题思路：

题目描述：

输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

数据范围： n<=1000

要求：空间复杂度 O(1)，时间复杂度 O(n)

例如，输入{1,2,3},{4,5},{6,7}时，两个无环的单向链表的结构如下图所示：

可以看到它们的第一个公共结点的结点值为6，所以返回结点值为6的结点。

输入描述：

输入分为是3段，第一段是第一个链表的非公共部分，第二段是第二个链表的非公共部分，第三段是第一个链表和二个链表的公共部分。 后台会将这3个参数组装为两个链表，并将这两个链表对应的头节点传入到函数FindFirstCommonNode里面，用户得到的输入只有pHead1和pHead2。

返回值描述：

返回传入的pHead1和pHead2的第一个公共结点，后台会打印以该节点为头节点的链表。

示例：

输入：

{1,2,3},{4,5},{6,7}

返回值：

{6,7}

说明：

第一个参数{1,2,3}代表是第一个链表非公共部分，第二个参数{4,5}代表是第二个链表非公共部分，最后的{6,7}表示的是2个链表的公共部分

这3个参数最后在后台会组装成为2个两个无环的单链表，且是有公共节点的  

解题思路：

本题考察数据结构链表的使用。将两个链表指针向前步进，走到头后就错位继续前进，因为两个指针行进的速度一致，走着走着就撞一起了，如下方gif动画所示，很直观。

测试代码：

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        ListNode *a=pHead1,*b=pHead2;
        while(a!=b)
        {
            a=a?a->next:pHead2;
            b=b?b->next:pHead1;
        }
        return a;
    }
};

到此这篇关于C++ 解决求两个链表的第一个公共结点问题的文章就介绍到这了,更多相关C++ 求两个链表的公共结点内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • 剑指offer之C++语言实现链表(两种删除节点方式)

    1 问题 用C++语言实现链表 2 代码实现 #include <iostream> #include <stdlib.h> using namespace std; class List { public: List(); ~List(); List* createNode(int value);//创建节点 bool insertNode(List *node);//插入节点 void printList();//打印节点 bool deleteNode(List *node)

  • C++删除链表中间节点的方法

    本文实例讲述了C++删除链表中间节点的方法.分享给大家供大家参考,具体如下: 题目: 给定链表头结点head,实现删除链表的中间节点函数. 解题思路及代码: 快慢指针,快指针走两步,慢指针一步. 当快指针走到终点时,慢指针正好是链表中间节点,删除此节点即可. 链表结构定义: typedef struct Node { int data; struct Node* next; }node, *pLinkedList; 算法C++代码: Node* removeMidNode(pLinkedList

  • C++实现LeetCode(19.移除链表倒数第N个节点)

    C++实现LeetCode(19.移除链表倒数第N个节点)

    [LeetCode] 19. Remove Nth Node From End of List 移除链表倒数第N个节点 Given a linked list, remove the nth node from the end of list and return its head. For example, Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the en

  • C++实现单链表删除倒数第k个节点的方法

    本文实例讲述了C++实现单链表删除倒数第k个节点的方法.分享给大家供大家参考,具体如下: 题目: 删除单链表中倒数第k个节点 解题思路及算法代码: 标尺法,定义两个指针指向链表头结点,先让一个走k步,然后两个指针同时开始走,当先走的指针走到末尾时,后走的指针指向的结点就是需要删除的结点. 单链表结构定义: typedef struct Node { int data; struct Node* next; }node, *pLinkedList; 删除倒数第K结点操作代码: //head表示头结

  • C++实现LeetCode(160.求两个链表的交点)

    [LeetCode] 160.Intersection of Two Linked Lists 求两个链表的交点 Write a program to find the node at which the intersection of two singly linked lists begins. For example, the following two linked lists: A:          a1 → a2 c1 → c2 → c3             B:     b1

  • C++ 解决求两个链表的第一个公共结点问题

    C++ 解决求两个链表的第一个公共结点问题

    目录 题目描述: 输入描述: 返回值描述: 示例: 解题思路: 题目描述: 输入两个无环的单向链表,找出它们的第一个公共结点,如果没有公共节点则返回空.(注意因为传入数据是链表,所以错误测试数据的提示是用其他方式显示的,保证传入数据是正确的) 数据范围: n<=1000 要求:空间复杂度 O(1),时间复杂度 O(n) 例如,输入{1,2,3},{4,5},{6,7}时,两个无环的单向链表的结构如下图所示: 可以看到它们的第一个公共结点的结点值为6,所以返回结点值为6的结点. 输入描述: 输入分

  • C++ 解决求两个链表的第一个公共结点问题

    目录 题目描述: 输入描述: 返回值描述: 示例: 解题思路: 补充 题目描述: 输入两个无环的单向链表,找出它们的第一个公共结点,如果没有公共节点则返回空.(注意因为传入数据是链表,所以错误测试数据的提示是用其他方式显示的,保证传入数据是正确的) 数据范围: n<=1000 要求:空间复杂度 O(1),时间复杂度 O(n) 例如,输入{1,2,3},{4,5},{6,7}时,两个无环的单向链表的结构如下图所示: 可以看到它们的第一个公共结点的结点值为6,所以返回结点值为6的结点. 输入描述:

  • python实现求两个字符串的最长公共子串方法

    如下所示: # coding:utf-8 ''' 求两个字符串的最长公共子串 思想:建立一个二维数组,保存连续位相同与否的状态 ''' def getNumofCommonSubstr(str1, str2): lstr1 = len(str1) lstr2 = len(str2) record = [[0 for i in range(lstr2+1)] for j in range(lstr1+1)] # 多一位 maxNum = 0 # 最长匹配长度 p = 0 # 匹配的起始位 for

  • C语言求两个字符串的最长公共子串

    本文实例讲述了C语言求两个字符串的最长公共子串的方法.分享给大家供大家参考.具体实现方法如下: #include "stdio.h" #include "string.h" #include "stdlib.h" void getCommon(char str1[],char str2[],char * str3); int stringLength(char * str); void main(){ char str1[50]; char st

  • C++将二叉树转为双向链表及判断两个链表是否相交

    C++将二叉树转为双向链表及判断两个链表是否相交

    把二叉查找树转变成排序的双向链表 例如: 转换成双向链表 4=6=8=10=12=14=16 struct BSTreeNode { int m_nValue; // value of node BSTreeNode *m_pLeft; // left child of node BSTreeNode *m_pRight; // right child of node }; 首先阐述下二叉排序树: 它首先要是一棵二元树,在这基础上它或者是一棵空树:或者是具有下列性质的二元树: (1)若左子树不空

  • C++解决合并两个排序的链表问题

    C++解决合并两个排序的链表问题

    目录 题目描述: 示例: 解题思路: 测试代码: 题目描述: 输入两个递增的链表,单个链表的长度为n,合并这两个链表并使新链表中的节点仍然是递增排序的. 数据范围: n为0~1000,节点值为-1000~1000 要求:空间复杂度 O(1),时间复杂度 O(n) 如输入{1,3,5},{2,4,6}时,合并后的链表为{1,2,3,4,5,6},所以对应的输出为{1,2,3,4,5,6},转换过程如下图所示: 或输入{-1,2,4},{1,3,4}时,合并后的链表为{-1,1,2,3,4,4},所

  • 逆转交替合并两个链表的解析与实现

    逆转交替合并两个链表的解析与实现

    逆转交替合并两个链表,即从一个链表的尾指针指向另一个链表的尾指针,依次逆转交替进行合并.下面就通过实例来详细的介绍该逆转交替合并两个链表的思路与实现代码. 一.问题描述 链表A和B A: 1->2->3->4 B: a->b->c->d 请逆转交替合并两个链表,示例结果如下: 4->d->3->c->2->b->1->a 节点类型定义如下: classNode { public Node next; ... } 二.源代码: 传

  • java实现字符串匹配求两个字符串的最大公共子串

    java实现字符串匹配求两个字符串的最大公共子串

    本文实例讲述了java实现求两个字符串最大公共子串的方法.分享给大家供大家参考,具体如下: 最近在项目工作中有一个关于文本对比的需求,经过这段时间的学习,总结了这篇博客内容:求两个字符串的最大公共子串. 算法思想:基于图计算两字符串的公共子串.具体算法思想参照下图: 输入字符串S1:achmacmh    输入字符串S2:macham 第a步,是将字符串s1,s2分别按字节拆分,构成一个二维数组: 二维数组中的值如b所示,比如第一行第一列的值表示字符串s2和s1的第一个字节是否相等,若相等就是1

  • 探讨:将两个链表非降序合并为一个链表并依然有序的实现方法

    已知两个链表list1和list,2,各自非降序排列,将它们合并成另外一个链表list3,并且依然有序,要求保留所有节点.实现过程中,list1中的节点和list2中的节点都转移到了list3中,注意泛型的友元函数的用法.程序如有不足之处,还望指正!!!定义List类 复制代码 代码如下: #include "stdafx.h"#include <iostream> using namespace std;template<class T>struct Node

随机推荐