LeetCode刷题(11)

发布时间:2023-05-15 08:30

链表相关问题

206. Reverse Linked List (Easy)

问题描述
给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

思路
非递归版:使用next指针保存head的下一个位置,pre保存为pre的上一个位置(初始化为空),head向后移动,每次移动时令head.next指向pre,之后使用pre保存当前位置,head移动到next的位置重复上述操作,直到head移动到为NULL的位置,此时pre变为了翻转链表的头指针。

递归版:
递归出口:if (head=null || head.next=null )return head;
将head和head.next看做两个部分,对head.next后面的链表进行反转,新链表的头指针为pre
然后让新链表的尾结点即head.next.next指向旧头结点:head.next.next=head
最后让head的后继节点指向空

代码(非递归版)

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null,next = null;
        while (head!=null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

代码(递归版)

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode nextHead = head.next;
        ListNode pre = reverseList(head.next);
        nextHead.next = head;
        head.next = null;
        return pre;
    }
}

21. Merge Two Sorted Lists (Easy)

问题描述

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

思路
非递归:创建一个新的链表头结点head,之后分别使用p,p1,p2指针指向head,listNode1,listNode2,然后将listNode1和listNode2中指向小的节点放在p的后继节点上,同时p向后移动,p1和p2中指向元素值小的那一个指针也同时向后移。当其中一个链表遍历完时,直接使用p.next指向未遍历完的链表当前遍历指针上,最后返回head.next作为新链表的头指针。

递归版:
递归出口:
if (list1 == null) { return list2; }
if (list2 == null) {return list1; }

将每个链表看做两个部分,首元素和head.next链表;
if(list1.val < list2.val),list1作为新链表的头结点,合并list1.next链表和list2链表;
if(list1.val >= list2.val),list2作为新链表的头结点,合并list2.next链表和list1链表;

代码(非递归)

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode p = list1,q = list2;
        ListNode newList = new ListNode(-1);
        ListNode newP = newList;
        while (p!=null && q!=null){
            if(p.val>q.val){
                newP.next = q;
                q = q.next;
                newP = newP.next;
            }else {
                newP.next = p;
                p = p.next;
                newP = newP.next;
            }
        }
        if(p!=null){
            newP.next = p;
        }
        if(q!=null){
            newP.next = q;
        }
        return newList.next;
    }
}

代码(递归)

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        if (list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

24. Swap Nodes in Pairs (Medium)

问题描述
给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。

输入输出样例

示例 1:

输入:head = [1,2,3,4]
输出:[2,1,4,3]
LeetCode刷题(11)_第1张图片

示例 2:

输入:head = []
输出:[]

思路
可以考虑先对前两个元素进行交换,确定好头结点的位置后,再对后面的元素经过两两交换。
交换的思路是:
LeetCode刷题(11)_第2张图片
当p移动到末尾位置或者为null时不再移动

代码

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next==null) return head;
        ListNode p = head;
        ListNode next = head.next;
        ListNode pre = null;
        p.next = next.next;
        next.next = p;
        pre = p;
        p = p.next;
        head = next;
        while (p != null && p.next!=null){
            next = p.next;
            p.next = next.next;
            next.next = p;
            pre.next = next;
            pre = p;
            p = p.next;
        }
        return head;
    }
}

160. Intersection of Two Linked Lists (Easy)

问题描述

给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。

图示两个链表在节点 c1 开始相交:

LeetCode刷题(11)_第3张图片
题目数据 保证 整个链式结构中不存在环。

思路
两个遍历指针分别指向两个链表开头,如果一个链表走到头则重新指向另外一个指针开头,这样当两个指针再次相遇时就是相交的位置。

代码

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p = headA;
        ListNode q = headB;
        while (p!=q){
            p = p==null?headB:p.next;
            q = q==null?headA:q.next;
        }
        return p;
    }
}

234. Palindrome Linked List (Easy)

问题描述
给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。

思路
先使用快慢指针找到链表中点,再把链表切成两半;然后把后半段翻转;最后比较两半是否相等。

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null)return true;
        ListNode fast=head,slow=head;
        while (fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        slow = reverse(slow);
        fast = head;
        while (slow!=null && fast!=null){
            if(slow.val != fast.val)return false;
            slow = slow.next;
            fast = fast.next;
        }
        return true;
        
    }
    
    private ListNode reverse(ListNode head){
        if(head == null || head.next==null) return head;
        ListNode newHead = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

83. Remove Duplicates from Sorted List (Easy)

问题描述
给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。

输入输出样例
示例 1:

输入:head = [1,1,2]
输出:[1,2]

示例 2:

输入:head = [1,1,2,3,3]
输出:[1,2,3]

问题描述
使用一个next指针每次直到当前指针的下一个位置,如果下一个位置的值等于当前位置的值,则删除next值向的元素(可能有多个连在一起,需要循环删除)

代码

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head==null || head.next==null)return head;
        ListNode p = head;
        ListNode next = null;
        while (p!=null){
            next = p.next;
            while (next!=null && next.val == p.val){
                p.next = next.next;
                next = p.next;
            }
            p = p.next;
        }
        return head;
    }
}

328. Odd Even Linked List (Medium)

问题描述
给定单链表的头节点 head ,将所有索引为奇数的节点和索引为偶数的节点分别组合在一起,然后返回重新排序的列表。
第一个节点的索引被认为是 奇数 , 第二个节点的索引为 偶数 ,以此类推。
请注意,偶数组和奇数组内部的相对顺序应该与输入时保持一致。
你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。

输入输出样例
示例 1:

输入: head = [1,2,3,4,5]
输出: [1,3,5,2,4]
LeetCode刷题(11)_第4张图片

示例 2:

输入: head = [2,1,3,5,6,4,7]
输出: [2,3,6,7,1,5,4]
LeetCode刷题(11)_第5张图片

思路
用两个指针p1,p2分别指向偶链表和奇链表的头结点,然后分别用p1.next.next和p2.next.next节点作为p1,p2的后继节点。然后p1,p2向后遍历,当p1,p2其中一个到达尾结点位置时停止遍历,之后直接将偶链表头指针作为p1的后继节点即可。

代码

class Solution {
    public ListNode oddEvenList(ListNode head) {
        if(head == null || head.next == null || head.next.next==null) return head;
        ListNode tailHead = head.next; 
        ListNode q = head;//偶数节点头指针
        ListNode p = tailHead; //技术节点头指针

        ListNode q1 = null;
        ListNode p1 = null;
        while (q.next!=null&&p.next!=null){
            q1 = q.next.next;
            p1 = p.next.next;
            q.next = q1;
            p.next = p1;
            q = q1;
            p = p1;
        }
        q.next = tailHead;
        return head;
    }
}

19. Remove Nth Node From End of List (Medium)

问题描述
给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。

思路
使用一个快指针比慢指针多k+1步,这样当快指针走到结尾时,只需要删除慢指针前面的数即可。

考虑一个特殊位置:如果第n个节点刚好是开头时,返回head.next即可。

代码

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode p = head;
        if(p==null) return null;
        for(int i=0;i<=n;i++){//快指针先向前走k+1步
            if(p==null) return head.next;//如果走到了空的位置,说明删除的是第一个节点
            p = p.next;
        }
        ListNode pre = head;
        while (p!=null){
            pre = pre.next;
            p = p.next;
        }
        pre.next = pre.next.next;
        return head;
    }
}

148. Sort List (Medium)

问题描述
给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。

思路
可以使用链表版的归并排序。即将链表从中间分成两个部分,分别对每个部分进行归并排序,之后将两个有序的链表合并在一起。从中间分开可以使用快慢指针,快指针指向结尾的时候,慢指针就指向了中间的位置。需要注意的点是,需要将两个链表从中间断开。

代码

class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null)return head;
        ListNode fast = head.next;
        ListNode slow = head;
        while (fast!=null && fast.next!=null){//快指针指向结尾或者为空时都结束
            fast = fast.next.next;
            slow = slow.next;
        }
        fast = slow.next;//fast重新指向了右边链表的头结点
        slow.next = null;//注意要断开两边的链表,否则下次递归时快慢指针会出问题
        ListNode listLeft = sortList(head);
        ListNode listRight = sortList(fast);
        return merge(listLeft,listRight);
    }
    
    //合并两个有序的链表
    public ListNode merge(ListNode list1,ListNode list2){
        if(list1 == null) return list2;
        if(list2 == null) return list1;
        if(list1.val<list2.val){
            list1.next = merge(list1.next,list2);
            return list1;
        }else {
            list2.next = merge(list1,list2.next);
            return list2;
        }
    }
}

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网,如有侵权请联系:561261067@qq.com

桂ICP备16001015号