devbox
小桥流水78
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构（Java）：力扣单链表面试OJ题_单链表逆置力扣题

作者：小桥流水78 | 2024-07-31 12:03:18

赞

踩

单链表逆置力扣题

1、题一：获取链表倒数第k个节点

. - 力扣（LeetCode）

1.1 思路解析

此题我们使用双指针法求解。

首先，我们要知道，倒数的第k个节点，距离倒数第一个节点还需要移动k-1次。

1.那么我们可以定义出两个指针，分别为fast和slow，他们初始均值均为头结点head。

2.先让fast指针向后移动k-1次，slow指针保持不动。

3.接着，fast指针和slow指针同步后移，直至fast指针指向最后一个节点。

4.此时，slow指针所指向的位置就是倒数第k个节点。

原理：这个解题思路的原理就是，fast指针和slow指针始终保持着k-1个移动次数，而当fast指针指向最后一个节点（即倒数第一个节点）时，那么slow指针指向的就是倒数第k个节点。

注意事项：

1.k的值是否合法 2.头指针head是否为null

1.2 代码

  1. public int kthToLast(ListNode head, int k) {
  2.         //当头指针为空时
  3.         if (head == null) {
  4.             return Integer.MAX_VALUE;
  5.         }
  6.  
  7.         //当k的值<=0时
  8.         ListNode cur = head;
  9.         int size = 0;
  10.         while (cur != null) {
  11.             size++;
  12.             cur = cur.next;
  13.         }
  14.         if (k <= 0) {
  15.             return Integer.MAX_VALUE;
  16.         }
  17.  
  18.         //双指针法求解
  19.         ListNode fast = head;
  20.         ListNode slow = head;
  21.  
  22.         //先让fast指针移动k-1次
  23.         int count = 0;
  24.         while (count != k - 1) {
  25.             fast = fast.next;
  26.             //当k值>size时（不合法），fast指针移动的k-1次中，必然会指向null
  27.             if (fast == null) {
  28.                 return Integer.MAX_VALUE;
  29.             }
  30.             count++;
  31.         }
  32.  
  33.         //slow和fast同步后移，直至fast指向倒数第一个元素（slow和fast始终保持k-1个移动次数）
  34.         while (fast.next != null) {
  35.             fast = fast.next;
  36.             slow = slow.next;
  37.         }
  38.         //返回val
  39.         return slow.val;
  40.     }

2、题二：逆置单链表

. - 力扣（LeetCode）

2.1 思路解析

此题我们使用头插法求解。

这道题的思路很简单：从第二个节点开始，每得到一个节点，将此节点进行头插操作。

注意：要将最开始的头结点的next置为null（因为链表的头节点在逆置后就变成了尾结点）

2.2 代码

  1. public ListNode reverseList(ListNode head) {
  2.         //当头结点head为空时
  3.         if (head == null) {
  4.             return head;
  5.         }
  6.         //获取第二个节点，将第一个节点的next置为null
  7.         ListNode cur = head.next;
  8.         head.next = null;
  9.         
  10.         //头插
  11.         while (cur != null) {
  12.             //先获取当前节点的下一个节点
  13.             ListNode curN = cur.next;
  14.             //将当前节点的next指向头结点（头插）
  15.             cur.next = head;
  16.             //将head更新为新头插的节点
  17.             head = cur;
  18.             //更新cur，继续头插
  19.             cur = curN;
  20.         }
  21.  
  22.         //返回逆置后的头结点
  23.         return head;
  24.     }

3、题三：移除链表元素（删除所有某一数值的节点，且一次循环）

. - 力扣（LeetCode）

3.1 思路解析

此题我们使用双指针法求解。

1.我们定义两个指针分别为prev（初始指向head头结点 即第一个节点）和cur（初始指向head的next节点 即第二个节点）。

2.遍历链表。

3.当cur所指节点的值为所要删除的val值时，cur向后移动，prev不动，且将prev的next指针指向移动后的cur，完成节点的删除。

4.若cur所指节点值不是所要删除的val值时，cur和prev同步后移一位。

5.当cur指向null时，遍历完成。

6.经过上述操作，除第一个节点外，其余的节点均已删除完成，我们只需额外判断第一个节点的值是否为要删除的val值即可。

3.2 代码

  1. public ListNode removeElements(ListNode head, int val) {
  2.         //当head为空时
  3.         if(head == null) {
  4.             return head;
  5.         }
  6.  
  7.         //双指针法求解
  8.         ListNode prev = head;
  9.         ListNode cur = head.next;
  10.  
  11.  
  12.         while (cur != null) {
  13.             //判断当前节点的值是否为要删除的val值
  14.             if (cur.val == val) {//若是，删除节点
  15.                 cur = cur.next;
  16.                 prev.next = cur;
  17.             }else {//若不是，均向后移动
  18.                 cur = cur.next;
  19.                 prev = prev.next;
  20.             }
  21.         }
  22.         //判断第一个节点的值是否我要删除的val值。
  23.         if (head.val == val) {
  24.             head = head.next;
  25.         }
  26.         //返回删除后的头结点
  27.         return head;
  28.     }

4、题四：获取链表的中间节点

. - 力扣（LeetCode）

 4.1 思路解析

此题我们使用快慢指针法求解。

1.首先，定义两个指针分别为fast和slow。

2.fast指针，每次向后移两位；slow指针，每次向后移一位。

3.链表元素个数为奇数时，当fast.next == null时，slow指向的节点就是中间节点；链表元素个数为偶数时，当fast == null时，slow指向的节点就是中间节点。

注意：

循环结束条件一定要写为：

while（fast != null && fast.next != null）

原因：

1.两者只要有一个不满足就要结束循环，说明已经找到了中间节点

2.一定要fast != null在前，避免fast.next时出现空指针异常

4.2 代码

  1. public ListNode middleNode(ListNode head) {
  2.         //快慢指针法求解
  3.         ListNode slow = head;
  4.         ListNode fast = head;
  5.         
  6.         //找中间节点
  7.         //一定要fast != null在前，避免出现空指针异常
  8.         //两个条件只要有一个不满足就结束循环，说明到了中间节点的位置
  9.         while (fast != null && fast.next != null) {
  10.             ListNode fastN = fast.next;
  11.             fast = fastN.next;
  12.             slow = slow.next;
  13.         }
  14.  
  15.         //返回中间节点
  16.         return slow;
  17.     }

5、题五：分割链表

给定 x, 把一个链表整理成前半部分小于 x, 后半部分大于等于 x 的形式

链表分割_牛客题霸_牛客网

5.1 思路解析

1.将链表进行遍历

2.将val < x的节点添加到新链表head1中

3.将val >= x的节点添加到新链表head2中

4.将head1和head2进行拼接

5.返回拼接后新表的头结点head1

注意：

1.无论如何，一定要将head2的最后一个节点next域置为null

2.当表中所以元素的val值都大于等于x时，那么head1将为空表，直接返回head2即可

5.2 代码

  1. public ListNode partition(ListNode pHead, int x) {
  2.         //当pHead为空时
  3.         if (pHead == null) {
  4.             return null;
  5.         }
  6.  
  7.         ListNode cur = pHead;
  8.         ListNode prev = null;
  9.         ListNode head1 = null;
  10.         ListNode head2 = null;
  11.         ListNode cur1 = null;
  12.         ListNode cur2 = null;
  13.  
  14.         //遍历链表 将val < x的节点添加到新表head1中
  15.         //将val >= x的节点添加到新表head2中
  16.         while (cur != null) {
  17.             if (cur.val < x) {
  18.                 if (head1 == null) {
  19.                     head1 = cur1 = cur;
  20.                 }else {
  21.                     cur1.next = cur;
  22.                     cur1 = cur1.next;
  23.                 }
  24.             }else {
  25.                 if (head2 == null) {
  26.                     head2 = cur2 = cur;
  27.                 }else {
  28.                     cur2.next = cur;
  29.                     cur2 = cur2.next;
  30.                 }
  31.             }
  32.             cur = cur.next;
  33.         }
  34.  
  35.         //注意：需要将head2的最后一个节点的next置为null
  36.         if(head2 != null) {
  37.             cur2.next = null;
  38.         }
  39.         //如果旧表中所有元素的val值都大于x，那么head1将会是空表，直接返回head2即可
  40.         if (head1 == null) {
  41.             return head2;
  42.         }
  43.         //将head1和head2进行拼接
  44.         cur1.next = head2;
  45.         return head1;
  46.     }

 6、题六：判断链表是否回文

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

6.1 思路解析

回文结构，其实就是对称结构：

 

当元素个数为奇数时：

1.找到中间节点（使用上面的例题已经讲到）

2.以中间节点为头，逆置其后链表

3.逆置后，链表存在下图结构，指针从两端开始比较val值是否相等，直到相遇时结束，若均相等则为回文结构。

当元素个数为偶数时：

1.偶数时，newH和slow无法相遇

2.我们只需额外判断 当 newH.next == slow 时，说明为回文结构。

6.2 代码

  1. public boolean chkPalindrome(ListNode A) {
  2.         // write code here
  3.         if (A == null) {
  4.             return true;
  5.         }
  6.         ListNode fast = A;
  7.         ListNode slow = A;
  8.  
  9.         //找中间节点
  10.         while (fast != null && fast.next != null) {
  11.             fast = fast.next.next;
  12.             slow = slow.next;
  13.         }
  14.  
  15.         //逆置中间节点后的链表
  16.         ListNode cur = slow.next;
  17.         ListNode curN = null;
  18.         while (cur != null) {
  19.             curN = cur.next;
  20.             cur.next = slow;
  21.             slow = cur;
  22.             cur = curN;
  23.         }
  24.  
  25.         //从两端开始遍历，比较值是否相等
  26.         ListNode newCur = A;
  27.         while (slow != newCur) {
  28.             if (slow.val != newCur.val) {
  29.                 return false;
  30.             }
  31.             if (newCur.next == slow) {
  32.                 return true;
  33.             }
  34.             slow = slow.next;
  35.             newCur = newCur.next;
  36.         }
  37.         return true;
  38.     }

7、题七：相交链表（找出相交节点）

. - 力扣（LeetCode）

7.1 思路解析 

首先，我们要知道，相交链表的形状为Y形，而非X形：

1.遍历求出各链表的长度，并求得长度的差值len。

2.将较长链表的头指针向后移动len个位置。

3.两个链表的头指针同时后移，会在交点处相遇。

7.2 代码

  1. public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
  2.         ListNode curA = headA;
  3.         ListNode curB = headB;
  4.         int lenA = 0;
  5.         int lenB = 0;
  6.         //求链表1的长度
  7.         while (curA != null) {
  8.             lenA++;
  9.             curA = curA.next;//curA发生改变
  10.         }
  11.         //求链表2的长度
  12.         while (curB != null) {
  13.             lenB++;
  14.             curB = curB.next;//curB发生改变
  15.         }
  16.         
  17.         //将curA和curB重新指向链表的起始位置
  18.         curA = headA;
  19.         curB = headB;
  20.         
  21.         //差值
  22.         int len = lenA - lenB;
  23.         
  24.         //将较长的链表头指针后移差值个长度
  25.         if (len < 0) {
  26.             len = -len;
  27.             while (len != 0) {
  28.                 curB = curB.next;
  29.                 len--;
  30.             }
  31.         }else {
  32.             while (len != 0) {
  33.                 curA = curA.next;
  34.                 len--;
  35.             }
  36.         }
  37.         
  38.         //相遇处即为交点
  39.         while (curA != curB) {
  40.             curA = curA.next;
  41.             curB = curB.next;
  42.         }
  43.         return curA;
  44.     }

8、题八：判断链表是否带环

. - 力扣（LeetCode）

8.1 思路解析 

此题我们使用快慢指针法求解。

1.定义fast为快指针，一次移动两个位置；slow为慢指针，一次移动一个位置。

2.若链表带环，那么这两个指针必定相遇（追击问题）。

注意：

因为fast一次走两步，slow一次走一步，那进入环中后，每次移动，fast和slow之间的距离必定缩短一个节点，那么必定相遇。

（若每次移动两者间缩短的距离不为1时，那么即使有环，也可能不会相遇）

8.2 代码

  1. public boolean hasCycle(ListNode head) {
  2.         ListNode fast = head;
  3.         ListNode slow = head;
  4.  
  5.         //判断是否相遇
  6.         while (fast != null && fast.next != null) {
  7.             fast = fast.next.next;
  8.             slow = slow.next;
  9.             if (fast == slow) {
  10.                 return true;
  11.             }
  12.         }
  13.         return false;
  14.     }

9、题九：求环的入口点

. - 力扣（LeetCode）

9.1 思路解析

设：
起点到入口点的长度为X
相遇节点到入口点长度为Y
环的长度为C

因为fast所走路程为slow所走路程的两倍
故：
X + n*C + (C - Y) = 2*(X + C - Y)
则：
X + (2-n)*C = Y
说明：相遇节点到入口点的距离和起点到入口点的距离相等
则，从相遇节点和起点开始相向而行，相遇时的节点就是入口点

注意:我们还需要处理不是环的情况！！！

9.2 代码

  1. public ListNode detectCycle(ListNode head) {
  2.          //head为空时
  3.          if (head == null) {
  4.              return head;
  5.          }
  6.  
  7.          ListNode fast = head;
  8.          ListNode slow = head;
  9.  
  10.          //确定相遇时的节点
  11.          while (fast != null && fast.next != null) {
  12.              fast = fast.next.next;
  13.              slow = slow.next;
  14.              if (fast == slow) {
  15.                  break;
  16.              }
  17.          }
  18.          //不是环
  19.          if (fast == null || fast.next == null) {
  20.              return null;
  21.          }
  22.          //从起点和相遇节点开始相向而行，相遇的节点就是入口点
  23.          ListNode curH = head;
  24.          while (curH != slow) {
  25.              curH = curH.next;
  26.              slow = slow.next;
  27.          }
  28.          return slow;
  29.      }

10、题十：合并两个有序链表

. - 力扣（LeetCode）

10.1 思路解析

思路很简单，就是从各链表起点开始遍历，比较val值，谁的值小，就插入到新链表当中。

若某一链表的元素全部插入新链表当中后，将另一链表剩余元素直接拼接即可。

10.2 代码

  1. public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
  2.         //链表为空时
  3.         if (list1 == null) {
  4.             return list2;
  5.         }
  6.         if (list2 == null) {
  7.             return list1;
  8.         }
  9.  
  10.         ListNode cur1 = list1;
  11.         ListNode cur2 = list2;
  12.         ListNode newH = null;
  13.         ListNode newCur = null;
  14.  
  15.         //从头遍历各链表 谁值小 谁就尾插到新链表中
  16.         while (cur1 != null && cur2 != null) {
  17.             if (cur1.val < cur2.val) {
  18.                 if (newH == null) {
  19.                     newH = newCur = cur1;
  20.                 }else {
  21.                     newCur.next = cur1;
  22.                     newCur = newCur.next;
  23.                 }
  24.                 cur1 = cur1.next;
  25.             }else {
  26.                 if (newH == null) {
  27.                     newH = newCur = cur2;
  28.                 }else {
  29.                     newCur.next = cur2;
  30.                     newCur = newCur.next;
  31.                 }
  32.                 cur2 = cur2.next;
  33.             }
  34.         }
  35.  
  36.         //某一链表的元素全部插入后，将另一链表剩余元素直接拼接即可
  37.         if (cur1 == null) {
  38.             newCur.next = cur2;
  39.         }
  40.         if (cur2 == null) {
  41.             newCur.next = cur1;
  42.         }
  43.         return newH;
  44.     }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小桥流水78/article/detail/908763
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号