1.合并两个有序链表

链接：

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

题目描述：

 

思路1：

遍历其中一个链表，分别进行头插，尾插和中间插入到另一个链表中

代码1： 

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    if (list1 == NULL && list2 == NULL)
    {
        return NULL;
    }
    if (list1 == NULL)
    {
        return list2;
    }
    if (list2 == NULL)
    {
        return list1;
    }
    struct ListNode* cur1 = list1; // 遍历list1链表
    struct ListNode* next1 = cur1->next; // cur1的下一个节点
    struct ListNode* cur2 = list2; // 遍历list2链表
    struct ListNode* next2 = cur2->next; // cur2的下一个节点
    while (cur2)
    {
        // 头插
        if (cur2->val <= list1->val) 
        {
            cur2->next = list1;
            cur1 = list1 = cur2;
            next1 = cur1->next;
            cur2 = next2;
            if (next2)
                next2 = next2->next;
        }
        // 尾插
        else if (cur2->val > cur1->val && next1 == NULL) 
        {
            cur1->next = cur2;
            return list1;
        }
        // 中间插入
        else if (cur2->val >= cur1->val && cur2->val <= next1->val) 
        {
            cur1->next = cur2;
            cur2->next = next1;
            cur1 = cur1->next;
            cur2 = next2;
            if (next2)
                next2 = next2->next;
        }
        else
        {
            cur1 = cur1->next;
            next1 = next1->next;
        }
    }
    return list1;
}

思路2：

利用归并排序的思维，遍历比较两个链表，将val小的节点链接到新的链表上

代码2：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    // 空链表直接返回
    if (list1 == NULL)
    {
        return list2;
    }
    if (list2 == NULL)
    {
        return list1;
    }
    struct ListNode* head = NULL;
    struct ListNode* tail = head; // 标记新链表的尾节点
    struct ListNode* cur1 = list1, * cur2 = list2; // 遍历比较两个链表
    // 归并排序
    while (cur1 && cur2)
    {
        if (cur1->val <= cur2->val)
        {
            // 第一次尾插
            if (head == NULL)
            {
                head = tail = cur1;
                cur1 = cur1->next;
            }
            else
            {
                tail->next = cur1;
                tail = tail->next;
                cur1 = cur1->next;
            }
        }
        else
        {
            // 第一次尾插
            if (head == NULL)
            {
                head = tail = cur2;
                cur2 = cur2->next;
            }
            else
            {
                tail->next = cur2;
                tail = tail->next;
                cur2 = cur2->next;
            }
        }
    }
    // cur1先遍历完就直接链接上cur2剩余部分，反之亦然
    if (cur1 == NULL)
    {
        tail->next = cur2;
    }
    if (cur2 == NULL)
    {
        tail->next = cur1;
    }
    return head;
}

2.链表分割

链接：

https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking

题目描述：

思路：

1.设置两个带头节点的新链表

2.将比x小的插入到A链表中，比x大的插入到B链表中

3.链接两个链表并返回，并释放头节点

代码：

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        // 设置两个带有哨兵卫的头节点
        struct ListNode* cur = pHead;
        struct ListNode* less_head, * less_tail, * greater_head, * greater_tail;
        less_head  = less_tail = (struct ListNode*)malloc(sizeof(struct ListNode));
        greater_head = greater_tail = (struct ListNode*)malloc(sizeof(struct ListNode));
 
        // 分别尾插到新链表
        while (cur)
        {
            if (cur->val < x)
            {
                less_tail->next = cur;
                less_tail = cur;
            }
            else
            {
                greater_tail->next = cur;
                greater_tail = cur;
            }
            cur = cur->next;
        }
        // 链表合并
        less_tail->next = greater_head->next;
        greater_tail->next = NULL;
        struct ListNode* head = less_head->next;
        free(less_head);
        free(greater_head);
        return head;
    }
};

3.回文链表

链接：

https://leetcode.cn/problems/palindrome-linked-list/ 

题目描述：

思路：

1.找到中间节点

2.反转一半的链表

3.将一半链表与另一半反转后的链表进行比较

代码： 

bool isPalindrome(struct ListNode* head){
    // 计算链表节点个数
    int num = 0;
    struct ListNode* cur = head;
    while (cur)
    {
        cur = cur->next;
        num++;
    }
    // 反转一半的链表
    cur = head;
    struct ListNode* newhead = NULL;
    int half_num = num / 2;
    while (half_num)
    {
        struct ListNode* next = cur->next;
        cur->next = newhead;
        newhead = cur;
        cur = next;
        half_num--;
    }
    // 比较
    if (num % 2 != 0)
    {
        cur = cur->next;
    }
    while (newhead)
    {
        if (newhead->val == cur->val)
        {
            cur = cur->next;
            newhead = newhead->next;
        }
        else
        {
            return false;
        }
    }
        return true;
}

4.相交链表

链接：

https://leetcode.cn/problems/intersection-of-two-linked-lists/ 

题目描述：

思路： 

1.分别计算两个链表的节点数目

2.让长链表先走节点数目的差距步

3.然后同时开始向后比较节点的地址 

代码： 

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    // 计算链表节点数
    int numA = 1, numB = 1;
    struct ListNode* curA = headA, * curB = headB;
    while (curA->next)
    {
        curA = curA->next;
        numA++;
    }
    while (curB->next)
    {
        curB = curB->next;
        numB++;
    }
    // 找出长链表和短链表
    struct ListNode* long_list = numA > numB ? headA : headB;
    struct ListNode* short_list = numA <= numB ? headA : headB;
    // 长链表走过两链表的差距步
    int gap = abs(numA - numB);
    while (gap--)
    {
        long_list = long_list->next;
    }
    // 比较两个链表的节点地址
    while (long_list && short_list)
    {
        if (long_list == short_list)
        {
            return long_list;
        }
        else
        {
            long_list = long_list->next;
            short_list = short_list->next;
        }
    }
    return NULL;
}

5.环形链表

链接：

https://leetcode.cn/problems/linked-list-cycle/submissions/ 

题目描述：

思路：

1.快指针一次走两步，慢指针一次走两步，这样在环中两个指针始终会相遇

代码： 

bool hasCycle(struct ListNode *head) {
    struct ListNode* slow = head, * fast = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
        {
            return true;
        }
        
    }
    return false;
}