【数据结构】单链表翻转及其应用

1. 首先单链表翻转是很好写出来的:

单链表翻转

答案:

// AC: Runtime: 0 ms, faster than 100.00% of Java online submissions for Reverse Linked List.
// Memory Usage: 38.7 MB, less than 62.83% of Java online submissions for Reverse Linked List.
// 递归反转,用一个临时 node 存储head的下一个节点。
// T:O(n), S:O(1)
// 
/**
 * 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 ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode temp = head;
        while (head != null) {
            temp = head.next;
            head.next = prev;
            prev = head;
            head = temp;
        }
        return prev;
    }
}


2. 接下来可以应用单链表的翻转,来解决另一问题:

Palindrome Linked List - LeetCode

两种解法:

解法一:O(n) 遍历并 O(n) 存储

// 法一:O(n) space 记录再对比法
// AC:
// Runtime: 7 ms, faster than 47.01% of Java online submissions for Palindrome Linked List.
// Memory Usage: 51.2 MB, less than 44.55% of Java online submissions for Palindrome Linked List.
// 略
// T:O(n), S:O(n)
// 
class Solution {
    public boolean isPalindrome(ListNode head) {
        List<Integer> record = new ArrayList<>();
        while (head != null) {
            record.add(head.val);
            head = head.next;
        }
        for (int i = 0; i < record.size() / 2; i++) {
            if (record.get(i).intValue() != record.get(record.size() - 1 - i).intValue()) {
                return false;
            }
        }
        return true;
    }
}


解法二:不用 O(n) 的存储,找到中间位置并翻转,得到原尾节点开头的翻转链表,再逐个对比:

// 方法二:O(1) space 中部翻转链表法
// AC: Runtime: 4 ms, faster than 96.87% of Java online submissions for Palindrome Linked List.
// Memory Usage: 48.8 MB, less than 82.03% of Java online submissions for Palindrome Linked List.
// 先找到链表中间位置,然后从中间位置翻转下半部分链表,得到原链表尾节点为头的翻转链表,再头尾逐个对比
// T:O(n), S:O(1)
// 
class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode tail = reverseList(slow);

        while (tail != null) {
            if (head.val != tail.val) {
                return false;
            }
            head = head.next;
            tail = tail.next;
        }
        return true;
    }

    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode temp = head;
        while (head != null) {
            temp = head.next;
            head.next = prev;
            prev = head;
            head = temp;
        }
        return prev;
    }
}


发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

«   2021年6月   »
123456
78910111213
14151617181920
21222324252627
282930
控制面板
您好,欢迎到访网站!
  查看权限
网站分类
搜索
最新留言
文章归档
网站收藏
友情链接

    Powered By Z-BlogPHP 1.5.2 Zero

    Copyright liuyang1.com. 转载文章,请注明出处。谢谢!