链表oj题2（Leetcode）（牛客）——合并两个有序链表；判断回文链表；链表分割

一，合并两个有序链表

合并两个有序链表（力扣）

1.1分析

这里合并两个链表，我们首先想到的思路就是构建一个新的链表，然后比较两个链表的val值的大小依次插入新链表，这里我们还需要注意几个细节

1. 如果其中一个链表是空的那那么我们直接返回另外一个非空的链表
2. 我们在比较插入的时候用的是while循环条件就是两个链表都不为空，那么如果一个链表已经结束了，那么我们再后面应该再把另外一条链表插入完。
   还有一些细节我在我的代码注释中有做标注。

2.2代码

truct 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=NULL;
    //开始进行插入组成新的链表
    while(list1&&list2)
    {
        if(list1->val<list2->val)
        {
            if(tail==NULL)
            {
                //第一次插入要分开处理
                head=tail=list1;
            }
            else
            {
                tail->next=list1;
                tail=tail->next;
            }
            list1=list1->next;
        }
        else
        {
            if(tail==NULL)
            {
                head=tail=list2;
            }
            else
            {
                tail->next=list2;
                tail=tail->next;
            }
            list2=list2->next;            
        }
    }
    //如果一个链表结束了那么另一个链表要继续插入
    if(list1)
    {
        tail->next=list1;
    }
    if(list2)
    {
        tail->next=list2;
    }
    return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

二，链表的回文结构

判断回文链表（力扣）

2.1分析

我们可以线取到中间的节点，然后把中间之后的链表反转，之后，把前面链表和后面的链表进行比较，即可得出。
注意我们这里需要两个函数：

1. 找到中间节点
2. 反转链表
   这个两个函数我的上一篇文章都有提到链表oj1

2.2代码

struct ListNode*reverseList(struct ListNode* head)
{
    struct ListNode*cur=head;
    struct ListNode*newhead=NULL;
    while(cur)
    {
        struct ListNode*next=cur->next;
        cur->next=newhead;
        newhead=cur;
        cur=next;
    }
    return newhead;
}

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode*slow=head;
    struct ListNode*fast=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
    }
    return slow;
}
bool isPalindrome(struct ListNode* head){
    //先找到中间节点，然后把后面的链表反转依次和前面的比较。
    struct ListNode*mid=middleNode(head);
    struct ListNode*rmid=reverseList(mid);
    while(rmid&&head)
    {
        if(rmid->val!=head->val)
        {
            return false;
        }
        rmid=rmid->next;
        head=head->next;
    }
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

三，链表分割

链表分割（牛客）

3.1分析

由于这个题目没有给我们具体的例子我们就自己找一个来观察。

我们假设3为分割数，我们的思路就是分成两个链表最后在链接在一起。分析链表就变成了以下两个链表。

同样的我们要注意特殊情况，如果上面的那个链表是空的呢？这种情况下我们就不能进行链接。所以我们在这里给这两个链表创建一个哨兵位，这样即使链表为空也可以正常的进行链接。有哨兵位还有一个优点就是当我们在进行插入的时候不用再特殊考虑链表为空的第一次插入。

这个图就是我们的思路的整合，这里还要注意一下，我们在最后要把哨兵位都去掉。

3.2代码

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        //创建哨兵位
        ListNode*lhead;
        ListNode*ltail;
        ListNode*ghead;
        ListNode*gtail;
        lhead=ltail=(ListNode*)malloc(sizeof(ListNode*));
        ghead=gtail=(ListNode*)malloc(sizeof(ListNode*));
        //开始比较
        ListNode*cur=pHead;
        while(cur)
        {
            if(cur->val<x)
            {
                ltail->next=cur;
                ltail=ltail->next;
            }
            else {
            gtail->next=cur;
            gtail=gtail->next;
            }
            cur=cur->next;
        }
        ltail->next=ghead->next;
        gtail->next=NULL;
        ListNode*head=lhead->next;//这一步就是把ihead这个哨兵位去掉
        free(lhead);
        free(ghead);
        return head;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

四，小结

链表oj题目还有几道题目，每一道题目我们都到细细的钻研，把细节的部分都标上注释，方便以后复习的时候看。