反转一个链表 | 链表的中间结点

2.反转一个链表＜难度系数⭐＞

📝 题述：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

💨 示例1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

💨 示例2：
输入：head = [1,2]
输出：[2,1]

💨 示例3：
输入：head = [ ]
输出：[ ]

🧷 平台：Visual studio 2017 && windows

🔑 核心思想：
思路1，调整节点指针的方向

思路2，头插

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

typedef int SLTDataType;

struct ListNode
{
	int val;
	struct ListNode *next;
};
//思路1
struct ListNode* reverseList1(struct ListNode* head)
{
	//空链表
    if(head == NULL)
        return head;
    struct ListNode* n1, *n2, *n3;
    n1 = NULL;
    n2 = head;
    n3 = head->next;

    while(n2)
    {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        //最后一次进来时，n3为空指针
        if(n3)
            n3 = n3->next;
    }
    return n1;
}
//思路2
struct ListNode* reverseList2(struct ListNode* head)
{
	struct ListNode *newnode, *cur, *next;
    newnode = NULL;
    cur = head;
    while(cur)
    {
        next = cur->next;   
        cur->next = newnode;
        newnode = cur;
        cur = next;
    }
    return newnode;
}
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;
	
	reverseList1(n1);
	reverseList2(n1);
	return 0;
}

3.链表的中间结点＜难度系数⭐＞

📝 题述：给定一个头结点为 head 的非空单链表，返回链表的中间结点。 如果有两个中间结点，则返回第二个中间结点。

💨 示例1：
输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。注意，我们返回了一个 ListNode 类型的对象 ans，这样：ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

💨 示例2：
输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

🧷 平台：Visual studio 2017 && windows

🔑 核心思想：
快慢指针，快指针走2步，慢指针走1步，当快指针走完后，慢指针的当前位置就是中间节点

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

typedef int SLTDataType;

struct ListNode
{
	int val;
	struct ListNode *next;
};
struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode *slow, *fast;
    slow = fast = head;
    //必须同时满足奇偶的条件
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->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;

	middleNode(n1);
	return 0;
}