Palindrome linked list and linked list intersection problem (intersecting with Xinyi people) do you really know?

Catalog

One . Palindrome list

  Two . Linked list intersection problem

---

One . Palindrome list

1. Corresponding letecode link ：

234. Palindrome list - Power button （LeetCode）

2. Title Description ：

3. Their thinking ：

1. Define a pointer traversal cur Traverse the entire linked list and put the pointer of the node of the linked list on the stack .

2.cur Reassign to zero head Traverse the linked list again and compare the values of the elements at the top of the stack one by one. If they are not equal, they will return false that will do .

3.cur Go to empty if you haven't returned false That means it's a palindrome linked list .

4. The corresponding code

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode*cur=head;
        stack<ListNode*>stk;
        while(cur){
            stk.push(cur);
            cur=cur->next;
        }
        cur=head;
       // Iterate again and compare with the elements in the stack 
       while(cur){
           if(cur->val!=stk.top()->val){
               return false;
           }
           cur=cur->next;
           stk.pop();
       }
       return true;
    }
};

The problem of using stack is very simple. Can you optimize the space . The above method needs to be saved n Can we only save nodes n/2 A the （ Suppose there is n Nodes ）, Of course, we can find the intermediate node of the linked list. If we put the second half of the intermediate node of the linked list on the stack . then cur Traverse the linked list and the top of the stack from the beginning A comparison can be made until the stack is empty .

Corresponding optimization code ：

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 It's an intermediate node 
        ListNode*cur=slow;
        while(cur){
            stk.push(cur);
            cur=cur->next;
        }
        cur=head;// Compare the elements in the stack from the beginning 
        while(!stk.empty()){
            if(cur->val!=stk.top()->val){
                return false;
            }
            stk.pop();
            cur=cur->next;
        }
        return true;

    }
};

But this is still not the optimal solution. Can the space complexity O（1） Well ？ Of course, let's introduce this method

We use [1,2,3,2,1] For example ：

 1. The first step is to find the intermediate node of the linked list and use the speed pointer

        

2. The second part slow nodal next Set the pointer to null and flip the following linked list

 3. The third part defines that two pointers start to traverse the linked list from the head and the tail. In the process of traversal, if the comparison is not equal, it will return false Until the end of an empty path, it means that the palindrome linked list returns true.

4. Restore the linked list

The corresponding code ：

/**
 * 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){// Find the middle node of the list 
            n2=n2->next->next;
            n1=n1->next;
        }
        // here n1 It is the intermediate node of the linked list 
         n2=n1->next;
         n1->next=nullptr;
         while(n2){// Flip list 
          ListNode*n3=n2->next;// Save the next node pointer 
          n2->next=n1;
          n1=n2;
          n2=n3;
         }
         // At this time, the head of the second half is 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;
         }

         // Restore the linked list 
         n2=n1->next;
         n1->next=nullptr;
         while(n2){
          n3=n2->next;
          n2->next=n1;
          n1=n2;
          n2=n3;
         }
         return ret;

    }
};

  Two . Linked list intersection problem

1. Corresponding letecode link

160. Intersecting list - Power button （LeetCode）

2. Title Description ：

 3. Their thinking ：

Linked list intersection is like falling in love. Two people who don't know each other walk together .

Method 1 ：

1. We first let a linked list traverse once and count its length .

2. We will traverse another linked list and reduce the length in the traversal process

3. If the memory addresses of the end nodes of the two linked lists are not equal, it means that they are not intersected

4. Let the long linked list go through the difference between the two linked lists first .

5. Then walk together until they are equal （ Please refer to the code for details. ）

4. The corresponding code ：

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode*curA=headA;
        ListNode*curB=headB;
        int num=0;// Record length 
        while(curA->next){
            ++num;
            curA=curA->next;
        }
        // Traverse the second list 
        while(curB->next){
           --num;
           curB=curB->next;
         }
         if(curB!=curA){// Disjoint 
             return nullptr;
         }
         curA=num>0?headA:headB;// Default curA Point to the long linked list 
         curB=curA==headA?headB:headA;
         num=abs(num);
         while(num>0){
           --num;
           curA=curA->next;
         }
         // At the same time through 
         while(curA!=curB){
             curB=curB->next;
             curA=curA->next;
         }
         return curA;
    }
};

Method 2 ： Double pointer

If the list has no intersections

The two lists are the same length , After the first traversal pA and pB All are nullptr, End traversal
The two linked lists are not the same length , After two iterations pA and pB All are nullptr, End traversal

  The corresponding code ：

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode*curA=headA;
        ListNode*curB=headB;
//  Either meet or the nodes are equal , Or they are all empty, that is, there is no fate or division , Finally, they can jump out of the emotional dead circle .
        while(curA!=curB){
            curB=curB?curB->next:headA;
            curA=curA?curA->next:headB;
        }
        return curA;

    }
};

Finally, if we increase the difficulty of the problem, how to deal with two single linked lists that may or may not have rings

1. If the two linked lists have no rings, we can directly use the above code at this time .

2. If a linked list has a ring and another linked list has no ring, the two linked lists must not intersect .

3. Both linked lists have rings. In addition, we need to find the ring entry nodes of the two linked lists , Before finding it, there are several situations .

The entry nodes of the two linked lists are the same .

The entry nodes of the two linked lists are different .

Be careful ：1. If the entry nodes of the two linked lists are the same, it is actually equivalent to the same linked list of the above question, but the end position of the above question is NULL, And here is the entry loop node .

          2. If the two linked list entry nodes are different, we select one entry node and let it roll back to us. If we encounter another entry node in this circle, we can return one at will . If not, it means that the two linked lists do not intersect at all .

The corresponding code ：

#include<iostream>
using namespace std;
struct Node {
	Node(int v)
		:next(nullptr)
		,value(v)
	{}
	int value;
	Node* next;
};
// Find his entry point 
Node* getLoopNode(Node* head) {
		if (head == nullptr || head->next == nullptr || head->next->next == nullptr) {
			return nullptr;
		}
		// n1  slow   n2  fast 
		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   meet 
		fast = head; // n2 -> walk again from head
		while (slow != fast) {
			slow = slow->next;
			fast = fast->next;
		}
		return slow;
	}
//  If both linked lists are acyclic , Returns the first intersection node , If you don't want to pay , return 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  :   Linked list 1 Length minus linked list 2 Value of length 
	cur1 = n > 0 ? head1 : head2; //  Who is long , Whose head becomes cur1
	cur2 = cur1 == head1 ? head2 : head1; //  Who is short , Whose head becomes 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);
	// Two linked lists have no rings 
	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;
}

Last ：

I hope you can understand the intersection of linked lists. I also wish you old tie can make friends with people who are happy with you. Come on and spend the rest of your life together .