数据结构-链表（java）(2)

请确定链接列表是否为回文链接列表.

示例1:

输入: 1->2
输出: false

示例2:

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

高级:

您可以用O（n）时间复杂度和O（1）空间复杂度解决此问题吗？

    /**
     * 断一个链表是否为回文链表
     * 输入: 1->2->2->1
     * 输出: true
     */
    public static boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        ListNode reverseNode = null;//指向反转的链表
        ListNode nomalNode;//指向后面后半截链表
        if (head.next.next == null) {
            reverseNode = head;
            nomalNode = head.next;
            reverseNode.next = null;
        } else {
            //快慢指针找中间值
            //顺便反转前半截链表
            ListNode slow = head;
            ListNode fast = head;
            ListNode tempSlow;
            ListNode tempFast;
            while (fast.next != null && fast.next.next != null) {
                tempSlow = slow.next;
                tempFast = fast.next.next;
                slow.next = reverseNode;
                reverseNode = slow;
                slow = tempSlow;
                fast = tempFast;
            }
            tempSlow = slow.next;
            slow.next = reverseNode;
            reverseNode = slow;
            //考虑链表是奇数长度链表
            if (fast.next == null) {
                reverseNode = reverseNode.next;
            }
            nomalNode = tempSlow;
        }
        //遍历后半截找不同
        while (nomalNode != null && reverseNode != null) {
            if (nomalNode.val != reverseNode.val) {
                return false;
            }
            nomalNode = nomalNode.next;
            reverseNode = reverseNode.next;
        }
        return true;

快慢指针: 可以找到环，可以找到中间点，还可以找到n个节点的链表.

双向链表的工作方式类似java 链表，但是还有一个参考字段，称为“上一个”字段. 通过此额外字段，您可以知道当前节点的上一个节点.

图片

// Definition for doubly-linked list.
class DoublyListNode {
    int val;
    DoublyListNode next, prev;
    DoublyListNode(int x) {val = x;}
}

类似于单链接列表，我们将使用头节点表示整个列表.

类似于单链列表，我们将介绍如何访问数据，插入新节点或删除双链列表中的现有节点.

我们无法在固定时间内访问随机位置. 我们必须从头开始经过才能获得所需的第一个节点. 在最坏的情况下，时间复杂度将为O（N），其中N是链​​表的长度.

如果要在现有节点prev之后插入新的节点cur，可以将此过程分为两个步骤:

将cur与prev和next链接，其中next是prev的原始下一个节点；

图片

使用cur重新链接上一个和下一个.

图片

如果要从双向链接列表中删除现有节点，则只需将其上一个节点prev与下一个下一个节点链接即可.

与单链列表不同，使用“ prev”字段可以很容易地在恒定时间内获取上一个节点.

由于我们不再需要遍历链表来获取前一个节点，因此时间和空间复杂度均为O（1）.

让我们简要回顾一下单链表和双链表的性能.

它们在许多操作中都是相似的.

他们俩都无法在恒定时间内随机访问数据. 他们可以在给定节点之后或O（1）时间的列表开头添加新节点. 他们可以在O（1）时间内删除第一个节点

但是，删除给定节点（包括最后一个节点）时，它会稍有不同.

在这里，我们比较链表和其他数据结构（包括数组，队列和堆栈）之间的时间复杂度:

图片

经过比较，得出结论并不困难:

将两个有序链接列表合并到一个新的有序链接列表中并返回. 新的链表由给定的两个链表的所有节点组成.

示例:

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

   /**
     * 合并两个有序链表
     */
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        
        ListNode temp1 = l1;
        ListNode temp2 = l2;
        ListNode mergeListNode;
        if (l1.val > l2.val) {
            mergeListNode = l2;
            temp2 = l2.next;
        } else {
            mergeListNode = l1;
            temp1 = l1.next;
        }
        ListNode mergeListNodePointer = mergeListNode;
        //每次循环只前进一个指针
        while (temp1 != null && temp2 != null) {
            if (temp1.val > temp2.val) {
                mergeListNodePointer.next = temp2;
                mergeListNodePointer=mergeListNodePointer.next;
                temp2 = temp2.next;
            } else {
                mergeListNodePointer.next = temp1;
                mergeListNodePointer=mergeListNodePointer.next;
                temp1 = temp1.next;
            }
        }
        //将剩余的节点拼接起来
        if (temp1 != null) {
            mergeListNodePointer.next = temp1;
        }
        if (temp2 != null) {
            mergeListNodePointer.next = temp2;
        }
        return mergeListNode;
    }

给出两个非空链表以表示两个非负整数. 数字的数量以相反的顺序存储，并且它们的每个节点仅存储一个数字. 将两个数字重新添加到新的链接列表中.

您可以假设，除了数字0外，这些数字都不会以零开头.

示例:

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

链接列表

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-197432-2.html