1. leetcode_21 - merge two ordered linked lists

Merge two ascending lists into a new ascending list and return. The new linked list is composed of all the nodes of the given two linked lists. 

Example 1:
Input: l1 = [1,2,4], l2 = [1,3,4]
Output:[1,1,2,3,4,4]

Example 2:
Input: l1 = [], l2 = []
Output:[]

Example 3:
Input: l1 = [], l2 = [0]
Output:[0] 

Tips:
The range of the number of nodes in the two linked lists is [0, 50]
-100 <= Node.val <= 100
l1 and l2 They are arranged in non decreasing order

https://leetcode-cn.com/problems/merge-two-sorted-lists/submissions/

solution

   create a new leading linked list to store the merged linked list. When merging two linked lists, compare the size of the node values of the two linked lists, and put those with smaller node values into the new linked list
   finally, analyze whether the two linked lists have all put the elements into the new linked list. If not, put the nodes into the new linked list in turn, and finally return the next pointer of the new linked list

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) 
{
	if (NULL == l1)
		return l2;
	if (NULL == l2)
		return l1;

	struct ListNode* pNew = (struct ListNode*)malloc(sizeof(struct ListNode));
	pNew->next = NULL;

	struct ListNode* pNewL = pNew;   // Tail node used to point to the new linked list

	// Insert the qualified nodes into the new linked list
	while (NULL != l1 && NULL != l2)
	{
		if (l1->val <= l2->val)
		{
			pNewL->next = l1;
			l1 = l1->next;
		}
		else
		{
			pNewL->next = l2;
			l2 = l2->next;
		}

		pNewL = pNewL->next;
	}

	// Put the remaining nodes into the new linked list in turn
	if (NULL != l1)
	{
		pNewL->next = l1;
	}
	else
	{
		pNewL->next = l2;
	}

	return pNew->next;
}

2. leetcode_86. - separated list

Give you a list of the head node head And a specific value x ，Please separate the linked list so that all the items less than x All nodes appear in the x Before the node of.
You should keep the initial relative position of each node in the two partitions.

Example 1:
Input: head = [1,4,3,2,5,2], x = 3
 Output:[1,2,2,4,3,5]

Example 2:
Input: head = [2,1], x = 2
 Output:[1,2]
 
Tips:
The number of nodes in the linked list is in the range [0, 200] within
-100 <= Node.val <= 100
-200 <= x <= 200

leetcode: https://leetcode-cn.com/problems/partition-list/

solution

   the requirement of the topic is to divide the linked list according to a certain value, so two leading linked lists can be constructed, which are divided into two cases. The nodes larger than val value and smaller than val value are respectively inserted into the two linked lists, and finally the two linked lists are merged, which is the desired linked list.

// Two leading linked lists are constructed, one is used to store nodes less than x, and the other is used to store nodes larger than x. the original size order will not be changed by tailing
// Finally, merge the two linked lists
struct ListNode* partition(struct ListNode* head, int x) 
{
	if (NULL == head || NULL == head->next)
		return head;

	struct ListNode lessL;
	lessL.next = NULL;
	struct ListNode moreL;
	moreL.next = NULL;

	struct ListNode* lessLL = &lessL;
	struct ListNode* moreLL = &moreL;

	// Constructing two new linked lists
	while (NULL != head)
	{
		if (head->val < x)
		{
			lessLL->next = head;
			lessLL = lessLL->next;
		}
		else
		{
			moreLL->next = head;
			moreLL = moreLL->next;
		}

		head = head->next;
	}

	// Splicing two linked lists
	lessLL->next = moreL.next;
	moreL.next = NULL;

	return lessL.next;
}

3. leetcode_234 palindrome linked list

Please judge whether a linked list is palindrome linked list.

Example 1:
input: 1->2
 output : false

Example 2 :
input : 1->2->2->1
 output : true

solution

   judge whether a linked list is a palindrome linked list. Because the palindrome linked list is symmetrical, the following method can be used.

1. Looking for the middle node of the linked list
2. The linked list after flipping the intermediate node
3. Bit by bit comparison, if different nodes are found, it is not palindrome structure

// Flip linked list
struct ListNode* reverseList(struct ListNode* head)
{
    if (NULL == head || NULL == head->next)
        return head;

    struct ListNode* pPre = NULL;
    struct ListNode* pCur = head;
    struct ListNode* pNext = NULL;

    while (pCur != NULL)
    {
        pNext = pCur->next;
        pCur->next = pPre;
        pPre = pCur;
        pCur = pNext;
    }

    return pPre;
}

// Find the middle node of the linked list
struct ListNode* middleNode(struct ListNode* head)
{
    if (head == NULL)
        return NULL;

    struct ListNode* fast = head;
    struct ListNode* slow = head;

    // If the length of the linked list is even, then fast goes to the last part and the fast point is just NULL to stop the loop
    // If the length of the linked list is odd, then fast goes to the last step, and the current node is not empty. At that time, fast > next > next is empty, which will cause an error, so make sure that fast > next is not empty
    while (fast != NULL && fast->next != NULL)
    {
        fast = fast->next->next;
        slow = slow->next;
    }

    return slow;
}

// The palindrome structure of the linked list is symmetric about the middle, so you can find the middle node of the linked list first
// Reverse the back link list. Note whether there are different nodes between the reverse link list and the front link list. If so, it must not be palindrome structure
bool isPalindrome(struct ListNode* head) 
{
    // The case that there is only one node in the linked list is absolutely palindrome structure
    if (NULL == head || NULL == head->next)
        return true;

    // If there are two nodes, judge whether the two nodes are the same, the same is palindrome structure
    if (head->next->next == NULL)
    {
        if (head->val == head->next->val)
            return true;
        else
            return false;
    }

    struct ListNode* pTmp = head;

    // Find the intermediate node
    struct ListNode* pMid = middleNode(head);

    // Split the linked list into two parts and reverse a part of the linked list at the same time
    struct ListNode* rear = pMid;
    pMid = NULL;

        // Reverse placement
    rear = reverseList(rear);

    // Comparison of inverted two part linked list
    while (NULL != rear && NULL != pTmp)
    {
        if (rear->val != pTmp->val)
            return false;

        rear = rear->next;
        pTmp = pTmp->next;
    }

    return true;
}

4. leetcode_160 intersecting linked list

Write a program to find the starting node where two single linked lists intersect.

	Such as the following two linked lists:
	At node c1 Start to intersect.

	Example 1:
	Input: intersectVal = 8, listA = [4, 1, 8, 4, 5], listB = [5, 0, 1, 8, 4, 5], skipA = 2, skipB = 3
	Output: Reference of the node with value = 8
	Input explanation: the value of the intersecting node is 8 (note that if two linked lists intersect, it cannot be 0). Starting from the respective header, the linked list A by[4, 1, 8, 4, 5]，Linked list B by[5, 0, 1, 8, 4, 5]. stay A There are two nodes before the intersecting nodes; stay B In, there are three nodes before the intersecting node.

	Example 2:
	Input: intersectVal = 2, listA = [0, 9, 1, 2, 4], listB = [3, 2, 4], skipA = 3, skipB = 1
	Output: Reference of the node with value = 2
	Input explanation: the value of intersection node is 2 (note that if two linked lists intersect, it cannot be 0). Starting from the respective header, the linked list A by[0, 9, 1, 2, 4]，Linked list B by[3, 2, 4]. stay A There are three nodes before the intersecting nodes; stay B In, there is one node before the intersecting node.

	Example 3:
	Input: intersectVal = 0, listA = [2, 6, 4], listB = [1, 5], skipA = 3, skipB = 2
	Output: null
	Input explanation: calculate from the respective header, linked list A by[2, 6, 4]，Linked list B by[1, 5]. Because the two linked lists do not intersect, so intersectVal Must be 0, and skipA and skipB It can be any value.
	Explanation: the two linked lists do not intersect, so return null. 

solution

   the intersection of two linked lists can be divided into three types: Y V L, because in the above structure, both linked lists intersect to a point, and the end nodes are the same after the intersection,
   how to judge whether two linked lists intersect? We only need to detect whether the last node of two linked lists is the same. If they are the same, the linked lists must intersect

Thinking:
Determine whether two linked lists intersect
   2. If it intersects, find the intersection point: calculate the length of two linked lists, let the longer linked list move the long short length first, and then the two linked lists move at the same time. If the two nodes have the same address, they intersect

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) 
{
   if (NULL == headA || NULL == headB)
   	return NULL;

   struct ListNode* pTmpA = headA;
   struct ListNode* pTmpB = headB;

   int lenA = 0;
   int lenB = 0;

   // 1. Judge whether two linked lists intersect
   while (pTmpA != NULL)
   {
   	pTmpA = pTmpA->next;
   	lenA++;
   }
   	
   while (pTmpB != NULL)
   {
   	pTmpB = pTmpB->next;
   	lenB++;
   }

   if (pTmpA != pTmpB)
   	return NULL;

   // 2. Find the intersection point
   	// First calculate the length difference between two linked lists
   int distance = lenA - lenB;
   	// Move one of the linked list pointers to the specified position
   pTmpA = headA;
   pTmpB = headB;
   if (distance < 0)
   {
   	while (distance++ < 0)
   		pTmpB = pTmpB->next;
   }
   else
   {
   	while (distance-- > 0)
   		pTmpA = pTmpA->next;
   }

   // Two pointers move at the same time to judge whether the address is the same
   while (pTmpA != NULL && pTmpB != NULL)
   {
   	if (pTmpA == pTmpB)
   		break;
   	pTmpA = pTmpA->next;
   	pTmpB = pTmpB->next;
   }

   return pTmpA;
}