IT评测·应用市场-qidao123.com

标题: 【LeetCode】简单链表题 [打印本页]

---

作者: 立山    时间: 2022-6-26 14:31
标题: 【LeetCode】简单链表题
文章目录

• 
  
  
  
  • 1.LeetCode203移除链表元素
    
  • 2.LeetCode206反转链表
    
  • 3.LeetCode876链表的中间结点
    
  • 4.LeetCode21合并两个有序链表
    
    
  
• 总结
  

提示：以下是本篇文章正文内容，下面案例可供参考
1.LeetCode203移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
删除结点的步骤:
1.找到该结点的前一个结点
2.进行删除操作
3.最后处理头结点也为要删除结点的操作
题解：

1. class Solution {
2.     public ListNode removeElements(ListNode head, int val) {
3.          //防止链表为空
4.         if(head == null)
5.             return null;
6.         ListNode prev = head;//prev作为要删除的前一个结点
7.         ListNode cur = head.next;//cur作为要删除的结点
8.         while (cur != null) {
9.             if(cur.val == val) {  //此时为要删除的情况
10.                 prev.next = cur.next;
11.                 cur = cur.next;
12.             }else {    //不删除的情况
13.                 prev = cur;
14.                 cur = cur.next;
15.             }
16.         }
17.         //最后处理头结点
18.         if(head.val == val) {
19.             head = head.next;
20.         }
21.         return head;
22.     }
23.     }

复制代码

2.LeetCode206反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
在遍历链表时，将当前结点的next 指针改为指向前一个结点。由于结点没有引用其前一个结点，所以我们必须先存储其前一个结点。在更改引用之前，还需要存储后一个结点。最后返回新的头引用。
在这里我们申请prev为一个结点，最初指向null，申请cur存储头结点

1. class Solution {
2.     public ListNode reverseList(ListNode head) {
3.         if(head==null){
4.             return null;
5.         }
6.         ListNode prev = null;
7.         ListNode cur = head;
8.           while (cur != null){
9.                //记录当前结点的下一个节点
10.               ListNode CurNext =cur.next;
11.               //然后将当前结点指向prev
12.               cur.next= prev;
13.               //prev和cur结点都前进一位
14.               prev = cur;
15.               cur=CurNext;
16.           }
17.           return prev;
19.     }
20. }

复制代码

3.LeetCode876链表的中间结点

给定一个 头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
对于这道题，我们可以采用双指针来解决，用两个指针 slow （慢指针）
与 fast（快指针） 一起遍历链表。slow 一次走一步，fast 一次走两步。fast速度是slow的2倍，所以路程也是2倍，那么当 fast 到达链表的末尾时，slow 必然位于中间（奇数位与中间，偶数位于第二个中间结点）。
题解：

1. class Solution {
2.     public ListNode middleNode(ListNode head) {
3.      //预防链表为空的情况
4.      if(head == null){
5.          return null;
6.      }
7.      ListNode fast = head;
8.      ListNode slow = head;
9.      while(fast!= null  && fast.next!= null){
10.          fast = fast.next.next;//fast走两步
11.          slow = slow.next;//slow走一步
12.      }
13.      return slow;
14.     }
15. }

复制代码

4.LeetCode21合并两个有序链表

解题步骤:
1.先申请一个虚拟结点，并且让tmp遍历链表
2.分别比较list1、list2数据大小
3.比完之后肯定有一个链表没被合并完，有一个链表已经合并完成。我们直接将链表末尾指向未合并完的链表即可
题解：

1. class Solution {
2.     public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
3.        ListNode newHead = new ListNode(0);//先申请虚拟结点
4.        ListNode tmp = newHead;
5.        while(list1!=null && list2!=null){
6.            if(list1.val < list2.val){
7.                tmp.next = list1;
8.                list1 = list1.next;
9.                tmp = tmp.next;
10.            }
11.            else{
12.                tmp.next = list2;
13.                list2 = list2.next;
14.                tmp = tmp.next;
15.            }
16.        }
17.        //并后list1和list2最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表
18.        if(list1==null){
19.            tmp.next = list2;
20.     }else{
21.         tmp.next = list1;
22.     }
23.     return newHead.next;
24. }
25. }

复制代码

---

总结


提示：以上就是关于链表的简单题

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

---

欢迎光临 IT评测·应用市场-qidao123.com (https://dis.qidao123.com/)

Powered by Discuz! X3.4