链表中倒数第k个节点 | 合并两个有序链表

1.链表中倒数第k个节点＜难度系数⭐＞

📝 题述：输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

💨 示例：
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5

🧷 平台：Visual studio 2017 && windows

🔑 核心思想：
快慢指针，快指针先走k步，此时它与慢指针相差的就是k步，然后快慢指针同时1步1步的走，直到快指针指向NULL，此时慢指针指向的节点就是目标节点

leetcode原题
牛客网原题

⚠ 这道题我在两个平台都做了下，按照常规的写法，发现它在leetcode能过的代码，在牛客网上却过不了

所以我们这里使用更严格的写法

#include<stdio.h>
#include<stdlib.h>

typedef int SLTDataType;

struct ListNode
{
	int val;
	struct ListNode *next;
};
struct ListNode* getKthFromEnd(struct ListNode* head, int k)
{
	if(k == 0)
        return NULL;
	struct ListNode *slow, *fast;
    slow = fast = head;
    //fast先走k步
    while(k--)
    {
		//如果k大于链表的长度
        if(fast == NULL)
            return NULL;    
        fast = fast->next;
    }
    //slow和fast同时走，直至fast指向空
    while(fast)
    {
        slow = slow->next;
        fast = fast->next;
    }
    
    return slow;
}
int main()
{
	struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n1->val = 1;

	struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n2->val = 2;

	struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n3->val = 3;

	struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n4->val = 4;

	struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n5->val = 5;
	
	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = n5;
	n5->next = NULL;

	getKthFromEnd(n1, 2);
	return 0;
}

2.合并两个有序链表＜难度系数⭐＞

📝 题述：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

💨 示例1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

💨 示例2：
输入：l1 = [], l2 = []
输出：[ ]

💨 示例3：
输入：l1 = [ ], l2 = [0]
输出：[0]

🧷 平台：Visual studio 2017 && windows

🔑 核心思想：
思路1，见下图

思路2，带哨兵位的头节点

在之前的文章中没有了解过什么是哨兵位头节点，在这里就了解下：

1️⃣ 哨兵位头节点，这个节点不存储有效数据；而非哨兵位头节点存储有效数据

2️⃣ 非哨兵位头节点如果要修改头指针，需要使用二级指针操作；而哨兵位头节点，则不会修改头指针，因为它不存储有效数据

3️⃣ 这种哨兵位头节点在实际中很少出现，包括哈希桶、临接表做子结构都是不带头的。其次就是OJ中给的链表都是不带头的(从上面做的这些题就可以看出)，所以我们在以后编码过程中，应该尽量使用不带头的

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>

typedef int SLTDataType;

struct ListNode
{
	int val;
	struct ListNode *next;
};
//思路1
struct ListNode* mergeTwoLists1(struct ListNode* l1, struct ListNode* l2)
{
	struct ListNode *n1 = l1, *m1 = l2;
	struct ListNode *newhead = NULL, *tail = NULL;
	//判断空链表
    if(l1 == NULL)
        return l2;
    if(l2 == NULL)
        return l1;
        
	while(n1 && m1)
	{
		if(n1->val < m1->val)
		{
			if(newhead == NULL)
			{
				newhead = tail = n1;
			}
			else
			{
				tail->next = n1;
				tail = n1;
			}	
			n1 = n1->next;		
		} 
		else
		{
			if(newhead == NULL)
			{
				newhead = tail = m1;
			}
			else
			{
				tail->next = m1;
				tail = m1;
			}
			m1 = m1->next;
		}
	}
	//链接上剩余的数据
    if(n1)
        tail->next = n1;
    if(m1)
        tail->next = m1;
        
    return newhead;
}
//思路2
struct ListNode* mergeTwoLists2(struct ListNode* l1, struct ListNode* l2)
{
	struct ListNode *n1 = l1, *m1 = l2;
	struct ListNode *newhead = NULL, *tail = NULL;
    //判断空链表
    if(l1 == NULL)
        return l2;
    if(l2 == NULL)
        return l1;
    //申请空间
    newhead = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
	while(n1 && m1)
	{
		if(n1->val < m1->val)
		{
			tail->next = n1;
			tail = n1;	
			n1 = n1->next;		
		} 
		else
		{
			tail->next = m1;
			tail = m1;
			m1 = m1->next;
		}
	}
    //链接上剩余的数据
    if(n1)
        tail->next = n1;
    if(m1)
        tail->next = m1;
    //这里返回的是不带哨兵位的头节点。其次malloc开辟了空间，就要主动释放，否则会内存泄漏
    struct ListNode* first = newhead->next;
    free(newhead);
    return first;
}
int main()
{
	struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n1->val = 1;

	struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n2->val = 2;

	struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n3->val = 4;

	n1->next = n2;
	n2->next = n3;
	n3->next = NULL;
	/*----------------------------------分割------------------------------------*/
	struct ListNode* m1 = (struct ListNode*)malloc(sizeof(struct ListNode));
	m1->val = 1;

	struct ListNode* m2 = (struct ListNode*)malloc(sizeof(struct ListNode));
	m2->val = 3;

	struct ListNode* m3 = (struct ListNode*)malloc(sizeof(struct ListNode));
	m3->val = 4;

	n1->next = n2;
	n2->next = n3;
	n3->next = NULL;
	
	mergeTwoLists1(n1, m1);
	mergeTwoLists2(n1, m1);
	
	return 0;
}