C++相交链表和反转链表详解

时间:2022-11-13 23:51:56

给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null 。

C++相交链表和反转链表详解

思路

简单来说,就是求两个链表交点节点的 指针。 这里同学们要注意,交点不是数值相等,而是指针相等。

为了方便举例,假设节点元素数值相等,则节点指针相等。

看如下两个链表,目前curA指向链表A的头结点,curB指向链表B的头结点:

C++相交链表和反转链表详解

我们求出两个链表的长度,并求出两个链表长度的差值,然后让curA移动到,和curB 末尾对齐的位置,如图:

C++相交链表和反转链表详解

此时我们就可以比较curA和curB是否相同,如果不相同,同时向后移动curA和curB,如果遇到curA == curB,则找到焦点。

否则循环退出返回空指针。

/**
* 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* curA=headA;
      ListNode* curB=headB;
      int lenA=0;
      int lenB=0;
      while(curA!=nullptr){  // 求链表A的长度
          lenA++;
          curA=curA->next;
      }
      while(curB!=nullptr){  // 求链表B的长度
          lenB++;
          curB=curB->next;
      }
      //现在的curA,curB已经指向最后一个节点了,需要重新指向头结点
      curA=headA;
      curB=headB; 
      if(lenA<lenB){  //假设链表A的长度大于链表B,否则交换
          swap(lenA,lenB);
          swap(curA,curB);
      }
      //gap是两个链表长度的差值
      int gap=lenA-lenB; // gap=lenA-lenB 错误,要有返回类型
      while(gap){     // 让curA和curB在同一起点上(末尾位置对齐)
          gap--;
          curA=curA->next;  
      }
      while(lenB){   // 遍历curA 和 curB,遇到相同则直接返回
          if(curA==curB)
              return curA; // return curA(val) 返回节点中的值,这个写法是错误的  直接return curA
          curA=curA->next;
          curB=curB->next;
          lenB--;
      } 
      return nullptr;  //没有交点则返回空
  }
};

 

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

示例 1:

输入:head = [1,2,3,4,5]

输出:[5,4,3,2,1]

示例 2:

输入:head = [1,2]

输出:[2,1]

示例 3:

输入:head = []

输出:[]

双指针思路

首先判断链表是否为空,为空则返回nullptr。

接下来定义一个cur指针,指向头结点,再定义一个pre指针,初始化为null。

然后就要开始反转了,首先要把 cur->next 节点用tmp指针保存一下,也就是保存一下这个节点。

为什么要保存一下这个节点呢,因为接下来要改变 cur->next 的指向了,将cur->next 指向pre ,此时已经反转了第一个节点了。

接下来,就是循环走如下代码逻辑了,继续移动pre和cur指针。

最后,cur 指针已经指向了null,循环结束,链表也反转完毕了。 此时我们return pre指针就可以了,pre指针就指向了新的头结点。

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
  ListNode* reverseList(ListNode* head) {
      if(head==nullptr)  //对空链表的判断
          return nullptr;
      ListNode* per=nullptr;
      ListNode* cur=head;
      ListNode* temp; //建立一个指针
      while(cur){  //没必要写 while(cur!=nullptr),写了这个还要判断cur,会浪费时间,直接cur就可以
          temp=cur->next; //保存cur的下一个节点
          cur->next=per; //cur的下一个节点指向per,实现反转
          per=cur;  //cur=per;错误,是把cur的节点赋值给per
          cur=temp; //temp=cur;错误,是把temp(原来的cur->next)的节点赋值给cur
      }
      return per;
  }
};

递归

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
  ListNode* reverse(ListNode* per,ListNode* cur){  //返回的是一个链表,其返回值是指针
      if(cur==nullptr)  //递归的终止条件
          return per;
      ListNode* temp=cur->next;
      cur->next=per;
      return reverse(cur,temp); // 调用要写return
  }
  ListNode* reverseList(ListNode* head) {
      if(head==nullptr) //链表判空
          return nullptr; 
      return reverse(NULL,head); // 调用要写return
  }
};

 

总结

本篇文章就到这里了,希望能给你带来帮助,也希望您能够多多关注服务器之家的更多内容!

原文链接:https://blog.csdn.net/weixin_49358890/article/details/119345662