通知 网站从因情语写改为晴雨,这个网站的模板也从calmlog_ex改为 whimurmur

leetcode探索之链表学习 经典问题

1070人浏览 / 1人评论 / | 作者:因情语写  | 分类: 设计模式与算法  | 标签: 设计模式与算法  /  leetcode

作者:因情语写

链接:https://www.qingyu.blue/article/247

声明:请尊重原作者的劳动,如需转载请注明出处


    在上一章中,我们介绍了如何在链表中使用双指针技巧。本章节中,我们将从如何反转单链表开始并进一步探索更多经典问题。

    反转链表

    让我们从一个经典问题开始:

反转一个单链表。

    一种解决方案是按原始顺序迭代结点,并将它们逐个移动到列表的头部。似乎很难理解。我们先用一个例子来说明我们的算法。

    算法概述

    让我们看一个例子:

    请记住,黑色结点 23 是原始的头结点。

    1. 首先,我们将黑色结点的下一个结点(即结点 6)移动到列表的头部:

    2. 然后,我们将黑色结点的下一个结点(即结点 15)移动到列表的头部:

    3. 黑色结点的下一个结点现在是空。因此,我们停止这一过程并返回新的头结点 15。

    更多

    在该算法中,每个结点只移动一次。

    因此,时间复杂度为 O(N),其中 N 是链表的长度。我们只使用常量级的额外空间,所以空间复杂度为 O(1)。

    这个问题是你在面试中可能遇到的许多链表问题的基础。如果你仍然遇到困难,我们的下一篇文章将更多地讨论实现细节。

    还有许多其他的解决方案。您应该熟悉至少一个解决方案并能够实现它。


    算法说明

    反转链表

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:

你可以迭代或递归地反转链表。你能否用两种方法解决这道题?

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    // 想法:头插法来反转
    public ListNode reverseList(ListNode head) {
        if(head == null){
            return head;
        }
        if(head.next == null)
		{
			return head;
		}

		ListNode newList = head;
		ListNode next = head.next;
		newList.next = null;
		ListNode temp;

		if(next.next != null)
		{
			temp = next.next;
		}
		else
		{
			next.next = newList;
			return next;
		}

		while(temp != null)
		{
			next.next = newList;
			newList = next;
			next = temp;
			temp = temp.next;
		}

		next.next = newList;
		newList = next;

		return newList;
    }

    用到三个指针来翻转,next指向链表当前元素,temp指向链表下个元素,newList指向表头,使当前元素next.next为表头newList,然后通过temp获取下个元素,一次循环后下个元素temp变成当前元素next,重复此操作。

    代码很冗长,繁琐,下面看一个更好的解法

public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }

    核心都是使用三个变量进行操作,cur指向当前元素,pre指向新表头,tmp指向下个元素,操作也相同,但十分简洁

    移除链表元素

删除链表中等于给定值 val 的所有节点。

示例:

输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5
// 两个指针,一个指向当前,一个指向前一个结点
    public ListNode removeElements(ListNode head, int val) {
        ListNode cur, pre;
        
        if(head == null){
            return null;
        }
        
        while(head != null && head.val == val){
            head = head.next;
        }
        
        cur = head;
        if(cur != null && cur.next != null){
            pre = cur;
            cur = cur.next;
            
            while(cur != null){
                if(cur.val == val){
                    pre.next = cur.next;
                    cur = cur.next;
                }else{
                    pre = pre.next;
                    cur = cur.next;
                }
                
            }
        }
        
        return head;
    }

    使用双指针pre,cur,当cur是给定val的结点时,利用pre从链表中删除cur,看其它一种解法

public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        while (head !=null && head.val == val) {
            head = head.next;
        }
        ListNode pointer = head;
        while (pointer != null) {
            if (pointer.next != null && pointer.next.val ==val) {
                pointer.next = pointer.next.next;
            } else {
                pointer = pointer.next;
            }
        }
        return head;
    }

    这里只用了一个变量pointer,利用pointer和它的next实现和双指针相同的操作

    奇偶链表

给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1),时间复杂度应为 O(nodes),nodes 为节点总数。

示例 1:

输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL

示例 2:

输入: 2->1->3->5->6->4->7->NULL 
输出: 2->3->6->7->1->5->4->NULL

说明:

  • 应当保持奇数节点和偶数节点的相对顺序。
  • 链表的第一个节点视为奇数节点,第二个节点视为偶数节点,以此类推。

 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    // 想法:node.next.next
    public ListNode oddEvenList(ListNode head) {
        ListNode headEven, even, tempOdd;
        
        if(head == null || head.next == null){
            return head;
        }
        
        tempOdd = head;
        even = head.next;
        headEven = even;
        
        while(even != null && even.next != null){
            tempOdd.next = even.next;
            tempOdd = tempOdd.next;
            
            even.next = tempOdd.next;
            even = even.next;
        }
        
        
        tempOdd.next = headEven;
        return head;
    }
}

    一个链表变成奇数项和偶数项元素的两个链表,再连接这两个链表,再看另一种解法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode oddEvenList(ListNode head) {
        if(head == null) return null;
        ListNode odd = head;
        ListNode evenHead = head.next;
        ListNode even = evenHead;
        while(odd.next != null && even.next != null){
            odd.next = odd.next.next;
            odd = odd.next;
            even.next = even.next.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }
}

    思路差不多,但更加简洁,没有了开始时特殊值处理

    回文链表

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false

示例 2:

输入: 1->2->2->1
输出: true

进阶:
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    // 想法:先取出val存到列表里,再比较列表中的值
    public boolean isPalindrome(ListNode head) {
        List<Integer> nums = new ArrayList<>();
        
        while(head != null){
            nums.add(head.val);
            head = head.next;
        }
        
        for(int i = 0; i < nums.size() / 2; i++){
            if(!nums.get(i).equals(nums.get(nums.size() - 1 - i))){
                return false;
            }
        }
        
        return true;
    }
}

    先取出val存到列表里,再看列表中的元素是不是回文的,但空间复杂度是O(n),看一种更好的方法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) {
        return true;
    }

    if (head.next.next == null) {
        return head.val == head.next.val;
    }

    ListNode fast = head.next;
    ListNode slow = head;

    while (fast.next != null) {
        // 不停的从slow的后一个开始遍历,直到找到值相同的节点
        // 一次完成后,再移动到原节点的下一个节点开始,继续重复上面的步骤
        if (fast.next.val == slow.val) {
            if (fast.next.next != null) {
                return false;
            }
            fast.next = null;
            slow = slow.next;
            fast = slow.next;
            if (fast == null || fast.val == slow.val) {
                return true;
            }
        } else {
            fast = fast.next;
        }
    }
    return false;
}
}

    这里假定链表中相同的元素最多出现两次(在对称的位置出现两次),用了两个指针,慢指针指向当前要比较的元素,快指针寻找其回文对称位置的元素,每次找到后,从链表中丢弃这个元素,这样使每次找到的回文对称位置的元素都是链表的最后一个元素,这样链表不断变短,最终链表中只剩一个元素或两个相同的元素时可以证明是回文链表,这里的空间复杂度是O(1)了,但时间复杂度变成了O(n²)


    小结 - 链表经典问题

    我们为你提供了几个练习。你可能已经注意到它们之间的相似之处了。这里我们提供一些提示:

    1. 通过一些测试用例可以节省您的时间。

    使用链表时不易调试。因此,在编写代码之前,自己尝试几个不同的示例来验证您的算法总是很有用的。

    2. 你可以同时使用多个指针。

    有时,当你为链表问题设计算法时,可能需要同时跟踪多个结点。您应该记住需要跟踪哪些结点,并且可以自由地使用几个不同的结点指针来同时跟踪这些结点。

    如果你使用多个指针,最好为它们指定适当的名称,以防将来必须调试或检查代码。

    3. 在许多情况下,你需要跟踪当前结点的前一个结点。

    你无法追溯单链表中的前一个结点。因此,您不仅要存储当前结点,还要存储前一个结点。这在双链表中是不同的,我们将在后面的章节中介绍。


亲爱的读者:有时间可以点赞评论一下

点赞(0) 打赏

全部评论

2020-04-29 11:18