【数据结构】链表OJ(二)

Yan-英杰的博客

悟已往之不谏知来者之可追

一、反转链表

二、合并两个有序链表

三、链表分割

四、链表的回文结构

一、反转链表

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

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

方法一:

代码解析：

struct ListNode* reverseList(struct ListNode* head){
    if(head == NULL)
    {
        return NULL;
    }
    struct ListNode* n1,*n2,*n3;
    n1 = NULL;
    n2 = head;
    n3 = n2->next;
    while(n2)
    {
        //翻转链表
        n2->next = n1;
        //迭代
        n1 = n2;
        n2 = n3;
        if(n3)   
          n3 = n3->next;
    }
    return n1;
}

画图解析:

注:该题使用到了三指针

方法二:

代码解析：

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

        //头插
        cur->next = newhead;
        newhead = cur;
        cur = next;

    }
    return newhead;
}

画图解析：

此方法采用头插方式

二、合并两个有序链表

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

示例 1：

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

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

    两个链表的节点数目范围是 [0, 50]
    -100 <= Node.val <= 100
    l1 和 l2 均按非递减顺序排列

代码解析：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    if(list1 == NULL)
    {
        return list2;
    }
    if(list2 == NULL)
    {
        return list1;
    }
    struct ListNode* cur1 = list1,*cur2 = list2;
    struct ListNode* head = NULL,*tail = NULL;
    while(cur1 && cur2)
    {
        if(cur1->val < cur2->val)
        {
            if(head == NULL)
            {
                head = tail = cur1;
            }
            else
            {
                tail->next = cur1;
                tail = tail->next;
            }
            cur1 = cur1->next;
        }
        else
        {
             if(head == NULL)
            {
                head = tail = cur2;
            }
            else
            {
                tail->next = cur2;
                tail = tail->next;
            }
            cur2 = cur2->next;
        }
    }
    if(cur1)
    {
        tail->next = cur1;
    }
    if(cur2)
    {
        tail->next = cur2;
    }
    return head;
}

画图解析:

三、链表分割

描述

现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

思路:

小于尾插到一个链表，大于等于尾插到另一个链表，再将两个链表链接起来

代码解析:

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        struct ListNode* gGurad,*gTail,*lGuard,*lTail;
        gGurad = gTail = (struct ListNode*)malloc(sizeof(struct ListNode));
        lGuard = lTail = (struct ListNode*)malloc(sizeof(struct ListNode));
        gTail->next = lTail->next = NULL;

        struct 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 = gGurad->next;
        gTail->next =NULL;
        pHead = lGuard->next;
        free(gGurad);
        free(lGuard);
        return pHead;
    }
};

画图解析:

此题我们需要用到哨兵位的头节点

四、链表的回文结构

描述

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

测试样例：

1->2->2->1
返回：true

代码解析：

//查找中间节点
struct ListNode* Mid(struct ListNode* Head) {
    struct ListNode* slow = Head;
    struct ListNode* fast = Head;


    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}


//链表逆置
struct ListNode* reverse(struct ListNode* Head)
{
    struct ListNode* cur = Head;
    struct ListNode* phead = NULL;
    while(cur)
    {
        struct ListNode* next = cur->next;
        cur->next = phead;
        phead = cur;
        cur = next;
    }
    return phead;
}


class PalindromeList {
  public:
    bool chkPalindrome(ListNode* A) {
        struct ListNode* MidList = Mid(A);
        struct ListNode* ReList = reverse(MidList);

        struct ListNode* pphead = A;
        struct ListNode* ppheadR = ReList;
        while(pphead && ppheadR)
        {
            if(pphead->val != ppheadR->val)
            {
                return false;
            }
            else
            {
                pphead = pphead->next;
                ppheadR = ppheadR->next;
            }
           
        }
        return true;
    }
};

画图解析：