当前位置：首页 > article >正文

【初阶数据结构篇】单链表OJ题（上篇）

article 2024/11/24 0:18:07

文章目录

须知

💬 欢迎讨论：如果你在学习过程中有任何问题或想法，欢迎在评论区留言，我们一起交流学习。你的支持是我继续创作的动力！

👍 点赞、收藏与分享：觉得这篇文章对你有帮助吗？别忘了点赞、收藏并分享给更多的小伙伴哦！你们的支持是我不断进步的动力！
🚀 分享给更多人：如果你觉得这篇文章对你有帮助，欢迎分享给更多对C++感兴趣的朋友，让我们一起进步！

前言：

本篇文章是一篇训练题，以锻炼自己的思维为主，题目相对较简单，便于小白入门算法，接下来将跟着小编探索算法在解题中的应用。

1. 链表分割

题目链接：链表分割_牛客题霸_牛客网

题目描述：

1.1 解题思路：

思路1：

创建新链表，两次循环判断，第一次将所有小于x的节点尾插到新链表中，第二次循环将所有大于x节点的值尾插到第一次循环结束后的链表中，再返回新链表的头结点即可。

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        ListNode* pcur1=pHead;
        ListNode* pcur2=pHead;
        ListNode* newHead,*newTail=(ListNode*)malloc(sizeof(ListNode));
        //第一次循环将所有小于x的节点尾插到新链表中
        while(pcur1)
        {
            if(pcur1->val<x)
            {
                newTail->next=pcur1;
                newTail=newTail->next;
            }
            pcur1=pcur1->next;
        }
         //第二次循环将所有大于x的节点尾插到新链表中
        while(pcur2)
        {
            if(pcur2->val>=x)
            {
                newTail->next=pcur2;
                newTail=newTail->next;
            }
            pcur2=pcur2->next;
        }
        return newHead->next;
    }
};

思路2：

创建两个大小链表，再两个链表收尾相连，最后防止出现死循环。

class Partition {
  public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        ListNode* l1, * l2;
        l1 = l2 = (ListNode*)malloc(sizeof(ListNode));
        ListNode* l3, * l4;
        l3 = l4 = (ListNode*)malloc(sizeof(ListNode));
        ListNode* pcur = pHead;
        while (pcur) {
            //小链表
            if (pcur->val < x) {
                l1->next = pcur;
                l1 = l1->next;
            }
            //大链表
            else {
                l3->next = pcur;
                l3 = l3->next;
            }
            pcur=pcur->next;
        }
 
        l1->next=l4->next;
        l3->next = NULL;
         ListNode* ret=l2->next;
        free(l2);
        free(l4);
        l2=l4=NULL;
        return ret;
    }
};

2. 链表回文结构

题目链接：链表的回文结构_牛客题霸_牛客网

题目描述：

2.1 解题思路：

思路1：

将链表中的元素放进数组中，然后使用"双指针"判断是否为回文结构

class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        // write code here
        ListNode* pcur=A;
        int i=0,arr[901];
        //将链表中的数据存入数组中
        while(pcur)
        {
            arr[i++]=pcur->val;
            pcur=pcur->next;
        }
        int left=0,right=i-1;
        while(left<right)
        {
            if(arr[left]!=arr[right])
            {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
};

思路2：

找中间节点，再将中间节点后半段进行翻转，再将前半段链表与翻转后半段链表的值依次进行比较。

import java.util.*;

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        // 1 使用快慢指针找到链表的中间节点
        ListNode slow = A;
        ListNode fast = A;
        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }

        //2 对后半段链表进行逆置操作
        ListNode reversed = reverse(slow);
        //3 比较判断回文
        while(reversed!=null && A!=null){
            if(reversed.val != A.val){
                return false;
            }else{
                reversed = reversed.next;
                A = A.next;
            }
        }
        //跳出while循环，表示比较完毕，返回是回文
        return true;
    }

    //链表翻转
    public ListNode reverse(ListNode A) {
        if(A==null) {return null;}
        ListNode n0=null;
        ListNode n1=A;
        ListNode n2=A.next;
        while(n1!=null){
            //指向翻转
            n1.next = n0;
            //指针赋值
            n0 = n1;
            n1 = n2;
            if(n2!=null){
                n2 = n2.next; //n2后移;存在最后一次n2已经为空的后移
            }

        }
        //返回n0
        return n0;
    }
}