一.回文链表

二.链表相交问题

一.回文链表

1.对应letecode链接：
234. 回文链表 - 力扣（LeetCode）

2.题目描述：

3.解题思路：

1.定义一个指针遍历cur遍历整个链表将链表的节点的指针放入栈中。

2.cur重新赋值为head再次遍历链表和栈顶元素的值一一比较如果不相等就返回false即可。

3.cur走到空如果还没有返回false那说明是回文链表。

4.对应代码

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode*cur=head;
        stack<ListNode*>stk;
        while(cur){
            stk.push(cur);
            cur=cur->next;
        }
        cur=head;
       //重新遍历一次和栈中元素比较
       while(cur){
           if(cur->val!=stk.top()->val){
               return false;
           }
           cur=cur->next;
           stk.pop();
       }
       return true;
    }
};

这题用栈十分的简单那能不能优化一下空间了。上面的方式需要存n个节点我们是否能够只存n/2个了（假设有n个节点），当然可以我们可以找到链表的中间节点如果将链表的中间节点后半部分放入栈中。然后cur从头遍历链表和栈顶的元素一一比较即可直到栈为空。

对应优化代码：

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        stack<ListNode*>stk;
        ListNode*slow=head;
        ListNode*fast=head;
        while(fast&&fast->next){
            fast=fast->next->next;
            slow=slow->next;
        }
        //slow为中间节点
        ListNode*cur=slow;
        while(cur){
            stk.push(cur);
            cur=cur->next;
        }
        cur=head;//从头开始和栈中元素比对
        while(!stk.empty()){
            if(cur->val!=stk.top()->val){
                return false;
            }
            stk.pop();
            cur=cur->next;
        }
        return true;

    }
};

但是这任然不是最优解空间复杂度能不能O（1）呢？当然可以下面我们来介绍一下这种方法

我们以[1,2,3,2,1]为例：

1.第一步找到这个链表的中间节点使用快慢指针

2.第二部将slow所在节点的next指针置空并将后面的链表翻转

3.第三部定义两个指针从头部和尾部开始遍历链表遍历的过程中进行比对不相等就返回false直到一个走到空结束说明是回文链表返回true.

4.恢复链表

对应代码：

/**
 * 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:
    bool isPalindrome(ListNode* head) {
        ListNode*n1=head;
        ListNode*n2=head;
        while(n2&&n2->next){//找到链表的中间节点
            n2=n2->next->next;
            n1=n1->next;
        }
        //此时n1就是链表的中间节点
         n2=n1->next;
         n1->next=nullptr;
         while(n2){//翻转链表
          ListNode*n3=n2->next;//保存下一个节点指针
          n2->next=n1;
          n1=n2;
          n2=n3;
         }
         //此时后半部分的头为n1
         ListNode*n3=n1;
         n2=head;
         bool ret=true;
         while(n3&&n2){
            if(n3->val!=n2->val){
                ret=false;
                break;
            }
            n3=n3->next;
            n2=n2->next;
         }

         //恢复链表
         n2=n1->next;
         n1->next=nullptr;
         while(n2){
          n3=n2->next;
          n2->next=n1;
          n1=n2;
          n2=n3;
         }
         return ret;

    }
};

二.链表相交问题

1.对应letecode链接
160. 相交链表 - 力扣（LeetCode）

2.题目描述：

3.解题思路：

链表相交就像谈恋爱一样两个不认识的人走着走着就走到了一起去了。

方法一：

1.我们先让一个链表遍历一次并统计他的长度。

2.我们再遍历另外一个链表遍历过程中将长度减减

3.如果两个链表的结尾节点的内存地址不相等那么说明不相交

4.让长的链表先走两个链表的差值。

5.然后再同时走直到他们相等（具体请看代码）

4.对应代码：

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode*curA=headA;
        ListNode*curB=headB;
        int num=0;//记录长度
        while(curA->next){
            ++num;
            curA=curA->next;
        }
        //遍历第二个链表
        while(curB->next){
           --num;
           curB=curB->next;
         }
         if(curB!=curA){//不相交
             return nullptr;
         }
         curA=num>0?headA:headB;//默认curA指向长链表
         curB=curA==headA?headB:headA;
         num=abs(num);
         while(num>0){
           --num;
           curA=curA->next;
         }
         //同时遍历
         while(curA!=curB){
             curB=curB->next;
             curA=curA->next;
         }
         return curA;
    }
};

方法二：双指针

如果链表没有交点

两个链表长度一样，第一次遍历结束后 pA 和 pB 都是 nullptr，结束遍历
两个链表长度不一样，两次遍历结束后 pA 和 pB 都是 nullptr，结束遍历

对应代码：

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode*curA=headA;
        ListNode*curB=headB;
// 要么相遇即节点相等，要么都为空即无缘无分，最终都能跳出感情的死循环。
        while(curA!=curB){
            curB=curB?curB->next:headA;
            curA=curA?curA->next:headB;
        }
        return curA;

    }
};

最后如果我们将题目的难度提高两个单链表可能有环也可能没环此时又该如何处理了

1.如果两个链表都没有环的话此时我们可以直接使用上面的代码即可。

2.如果一个链表有环而另外一个链表无环此时这两个链表一定不可能相交。

3.两个链表都有环此外我们需要两个链表的入环节点找到，找到之前又分几种情况。

两个链表的入环节点相同。

两个链表的入环节点不相同。

注意：1.如果两个链表的入环节点相同其实也就等价于上题的链表相同只是上面那题的结尾位置是NULL，而在这里是入环节点。

2.如果两个链表入环节点不相同我们选择一个入环节点让其走一卷回到自己如果再这一圈中遇到了另外一个入环节点那么随意返回一个即可。如果没有遇到说明这两个链表根本就不相交。

对应代码：

#include<iostream>
using namespace std;
struct Node {
	Node(int v)
		:next(nullptr)
		,value(v)
	{}
	int value;
	Node* next;
};
//找到他的入环节点
Node* getLoopNode(Node* head) {
		if (head == nullptr || head->next == nullptr || head->next->next == nullptr) {
			return nullptr;
		}
		// n1 慢  n2 快
		Node* slow = head->next; // n1 -> slow
		Node* fast = head->next->next; // n2 -> fast
		while (slow != fast) {
			if (fast->next == nullptr || fast->next->next == nullptr) {
				return nullptr;
			}
			fast = fast->next->next;
			slow = slow->next;
		}
		// slow fast  相遇
		fast = head; // n2 -> walk again from head
		while (slow != fast) {
			slow = slow->next;
			fast = fast->next;
		}
		return slow;
	}
// 如果两个链表都无环，返回第一个相交节点，如果不想交，返回null
 Node* noLoop(Node *head1, Node *head2) {
	if (head1 == nullptr || head2 == nullptr) {
		return nullptr;
	}
	Node* cur1 = head1;
	Node* cur2 = head2;
	int n = 0;
	while (cur1->next != nullptr) {
		n++;
		cur1 = cur1->next;
	}
	while (cur2->next != nullptr) {
		n--;
		cur2 = cur2->next;
	}
	if (cur1 != cur2) {
		return nullptr;
	}
	// n  :  链表1长度减去链表2长度的值
	cur1 = n > 0 ? head1 : head2; // 谁长，谁的头变成cur1
	cur2 = cur1 == head1 ? head2 : head1; // 谁短，谁的头变成cur2
	n = abs(n);
	while (n != 0) {
		n--;
		cur1 = cur1->next;
	}
	while (cur1 != cur2) {
		cur1 = cur1->next;
		cur2 = cur2->next;
	}
	return cur1;
}

 Node* bothLoop(Node* head1, Node* loop1, Node* head2, Node* loop2) {
	 Node* cur1 = nullptr;
	 Node* cur2 = nullptr;
	 if (loop1 == loop2) {
		 cur1 = head1;
		 cur2 = head2;
		 int n = 0;
		 while (cur1 != loop1) {
			 n++;
			 cur1 = cur1->next;
		 }
		 while (cur2 != loop2) {
			 n--;
			 cur2 = cur2->next;
		 }
		 cur1 = n > 0 ? head1 : head2;
		 cur2 = cur1 == head1 ? head2 : head1;
		 n = abs(n);
		 while (n != 0) {
			 n--;
			 cur1 = cur1->next;
		 }
		 while (cur1 != cur2) {
			 cur1 = cur1->next;
			 cur2 = cur2->next;
		 }
		 return cur1;
	 }
	 else {
		 cur1 = loop1->next;
		 while (cur1 != loop1) {
			 if (cur1 == loop2) {
				 return loop1;
			 }
			 cur1 = cur1->next;
		 }
		 return nullptr;
	 }

 }

Node* getIntersectNode(Node* head1, Node* head2) {
		if (head1 == nullptr || head2 == nullptr) {
		return nullptr;
	    }
	Node* loop1 = getLoopNode(head1);
	Node *loop2 = getLoopNode(head2);
	//两个链表无环
	if (loop1 == nullptr && loop2 == nullptr) {
		return noLoop(head1, head2);
	}
	if (loop1 != nullptr && loop2 != nullptr) {
		return bothLoop(head1, loop1, head2, loop2);
	}

	return nullptr;
}

int main()
{
	return 0;
}

最后：

希望大家能够理解链表相交也祝各位老铁能和自己心怡的人相交一起加油一起走过余生。

回文链表及链表相交问题（和心怡的人相交）你真的会了吗？

一.回文链表

二.链表相交问题

相关文章

热门标签

最新文章