数据结构——链表题型练习(java版) 数据结构练习题

今天我们来刷题,给大家带来了与链表,栈,队列有关的试题,接下来我会放上题目链接,大家先自己尝试,再看讲解,希望对大家有帮助。

118. 杨辉三角 - 力扣(LeetCode)

这道题和我们平常做的,不一样,我们要返回链表,我们用顺序表来做,我说下大致思路哈。

我们要创建一个顺序表,顺序表每个下标也存一个小顺序表,就像二维数组一样,大顺序表是allList,小顺序表为arrayList,在小顺序表的头尾节点都放上1,再根据大顺序表行数补充小顺序表中间的数字。

class Solution {
 public List generate(int numRows) {
 List allList = new ArrayList();
 List arrayList = new ArrayList();
 arrayList.add(1);
 allList.add(arrayList);
 for(int i=1;i

876. 链表的中间结点 - 力扣(LeetCode)

下一道,获取链表的中间节点,这题是有技巧的,我们可以使用快慢指针,快指针走两步,慢指针走一步,无论是奇数还是偶数,当快指针走到null的时候,慢指针总为中间节点或者偶数时,两个中间节点的第二个。

class Solution {
 public ListNode middleNode(ListNode head) {
 ListNode fast = head;
 ListNode slow = head;
 while(fast!=null & fast.next!=null){
 fast = fast.next.next;
 slow = slow.next;
 }
 return slow;
 }
}

这题要注意,快指针判断为空的条件前后不能调换,不然fast为空的时候再.next就会空指针异常了。

203. 移除链表元素 - 力扣(LeetCode)

这道题我们使用双指针法,遍历这个链表,如果不是val我们就两个指针都往后走一步,是我们就删掉它,让val的前后指针相连,最后再判断头指针是否为value。

class Solution {
 public ListNode removeElements(ListNode head, int val) {
 if(head==null){
 return null;
 }
 ListNode pcur = head.next;
 ListNode plist = head;
 while(pcur!=null){
 if(pcur.val==val){
 plist.next = pcur.next;
 pcur = plist.next;
 }
 else{
 pcur = pcur.next;
 plist = plist.next;
 }
 }
 if(head.val==val){
 head = head.next;
 }
 return head;
 }
}

双指针法是最基础的算法,一定要掌握好

206. 反转链表 - 力扣(LeetCode)

翻转链表,我们有很多方法,可以创建新链表头插,但是我们如果要求不创建新的链表,空间复杂度为O(1)呢,我们只需要三个指针来遍历它即可。

class Solution {
 public ListNode reverseList(ListNode head) {
 if(head==null){
 return null;
 }
 ListNode l1 = null;
 ListNode l2 = head;
 ListNode l3 = head.next;
 while(l2!=null){
 l2.next = l1;
 l1 = l2;
 l2 = l3;
 if(l3!=null){
 l3 = l3.next;
 }
 }
 return l1;
 }
}

下面我们来用图描绘这一过程

直到

结束循环。

链表分割_牛客题霸_牛客网 (nowcoder.com)

这道题我们要分割链表,我们可以创建两个小链表,一个链表存小于目标值的,

另一个链表存大于目标值的,最后将两个链表连接起来。感觉挺简单,但是涉及到的细节很多的。

public class Partition {
 public ListNode partition(ListNode pHead, int x) {
 if(pHead==null){
 return null;
 }
 ListNode pcurFirst = null;
 ListNode pcurLast = null;
 ListNode plistFirst = null;
 ListNode plistLast = null;
 ListNode cur = pHead;
 while(cur!=null){
 if(cur.val

尤其注意当链表循环结束之后,我们要首先判断第一个链表是否为空,如果为空,那么就返回第二个链表,成功链接两个链表之后,判断第二个链表是否为空,如果为不为空就把第二个链表的末尾的next置为空。这个很关键,不然链表从头到尾没有null会无限循环。

链表的回文结构_牛客题霸_牛客网 (nowcoder.com)

这道题让我们判断链表是否回文,我们还是可以再创建一个链表来做,当然我们可以提高下难度,就用原链表。

我们首先,用快慢指针找到中间节点,中间节点右边的节点全部逆转,再从左和右开始遍历链表,判断是否回文。

public class PalindromeList {
 public boolean chkPalindrome(ListNode A) {
 ListNode fast = A;
 ListNode slow = A;
 ListNode l1 = null;
 ListNode l2 = null;
 ListNode l3 = null;
 ListNode cur = A;
 while(fast!=null & fast.next!=null){
 fast = fast.next.next;
 slow = slow.next;
 }
 l1 = slow;
 l2 = slow.next;
 l3 = l2.next;
 while(l2!=null){
 l2.next = l1;
 l1 = l2;
 l2 = l3;
 if(l3!=null){
 l3 = l3.next;
 }
 }
 while(l1.val!=cur.val){
 if(l1.val!=cur.val){
 return false;
 }
 l1 = l1.next;
 cur = cur.next;
 }
 return true;
 }
}

还是都是前面的方法,不难的,好好研究一下。

160. 相交链表 - 力扣(LeetCode)

链表相交,我们先来想想链表怎么相交

大家猜猜哪个是链表相交的正确形式呢,是右边的,链表相交的时候比的是地址,两个链表都引用

了相同地址的链表。所以我们只要遍历链表找到相同地址的节点不就完了吗,但是有个问题,就是如果就像题目中的那个链表,两个链表正好相差了一个节点,遍历的时候正好错过了,我们该怎么做呢,大链表减小链表长度,完了让大链表提前走一个节点就好了,我们直接上代码。

public class Solution {
 public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
 int length1 = 0;
 int length2 = 0;
 ListNode cur1 = headA;
 ListNode cur2 = headB;
 while(cur1!=null){
 length1++;
 cur1 = cur1.next;
 }
 cur1 = headA;
 while(cur2!=null){
 length2++;
 cur2 = cur2.next;
 }
 cur2 = headB;
 int len = length2-length1;
 if(len0){
 len--;
 cur2 = cur2.next;
 }
 while(cur1!=null & cur2!=null){
 if(cur1==cur2){
 return cur1;
 }
 cur1 = cur1.next;
 cur2 = cur2.next;
 }
 return null;
 }
}

中间用了个len判断它的大小,保证第二个链表长度大于第一个。

141. 环形链表 - 力扣(LeetCode)

这道题依然有一个技巧,有一个算法跟快慢指针一样,定义两个指针,一个走两步,一个走一步,如果相遇了那么这个链表带环,如果套圈,或者没有,链表都不成环。

public class Solution {
 public boolean hasCycle(ListNode head) {
 ListNode fast = head;
 ListNode slow = head;
 while(fast!=null & fast.next!=null){
 fast = fast.next.next;
 slow = slow.next;
 if(fast==slow){
 return true;
 }
 }
 return false;
 }
}

142. 环形链表 II - 力扣(LeetCode)

这道题涉及到了数学知识,

我们好好分析下这个带环链表

起点到入口点的距离我们设为x1,入口点到相遇点的距离我们设为x2。

fast一次走两步,slow一次走一步,我们算出fast指针走过的距离和slow走过的距离,fast走出的路程是slow的两倍,所以我们可以推导出x1与x2的关系恒等式,N的意思是fast可能会在环里走很多圈来等slow.

public class Solution {
 public ListNode detectCycle(ListNode head) {
 if(head==null){
 return null;
 }
 ListNode fast = head;
 ListNode slow = head;
 Boolean a = false;
 while(fast!=null & fast.next!=null){
 fast = fast.next.next;
 slow = slow.next;
 if(fast==slow){
 a = true;
 break;
 }
 }
 if(a!=true){
 return null;
 }
 slow = head;
 while(slow!=fast){
 slow = slow.next;
 fast = fast.next;
 
 }
 return slow;
 }
}

作者:神秘的t原文地址:https://blog.csdn.net/2301_79083481/article/details/141788136

%s 个评论

要回复文章请先登录注册