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

118. 杨辉三角 - 力扣（LeetCode）

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

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

<code>class Solution {

public List<List<Integer>> generate(int numRows) {

List<List<Integer>> allList = new ArrayList<>();

List<Integer> arrayList = new ArrayList<>();

arrayList.add(1);

allList.add(arrayList);

for(int i=1;i<numRows;i++){

List<Integer> arrayList2 = new ArrayList<>();

arrayList2.add(1);

for(int j=1;j<i;j++){

int value1 = allList.get(i-1).get(j-1);

int value2 = allList.get(i-1).get(j);

arrayList2.add(value1+value2);

}

arrayList2.add(1);

allList.add(arrayList2);

}

return allList;

}

}

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<x){

if(pcurFirst==null){

pcurFirst = pcurLast = cur;

}

else{

pcurLast.next = cur;

pcurLast = pcurLast.next;

}

}

else{

if(plistFirst==null){

plistFirst = plistLast = cur;

}

else{

plistLast.next = cur;

plistLast = plistLast.next;

}

}

cur = cur.next;

}

if(pcurFirst==null){

plistLast.next = null;

return plistFirst;

}

pcurLast.next = plistFirst;

if(plistFirst!=null){

plistLast.next=null;

}

return pcurFirst;

}

}

尤其注意当链表循环结束之后，我们要首先判断第一个链表是否为空，如果为空，那么就返回第二个链表，成功链接两个链表之后，判断第二个链表是否为空，如果为不为空就把第二个链表的末尾的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）

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

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

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

<code>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(len<0){

len = length1 - length2;

ListNode tmp = cur1;

cur1 = cur2;

cur2 = tmp;

}

while(len>0){

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.

<code>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;

}

}