数据结构-链表（java）

数据结构和算法

// Definition for singly-linked list.
public class SinglyListNode {
    int val;
    SinglyListNode next;
    SinglyListNode(int x) { val = x; }
}

如果要在给定节点prev之后添加新值，我们应该:

与数组不同，我们不需要将所有元素都移到插入的元素之后，因此您可以以O（1）时间复杂度将新节点插入到链表中，这非常有效.

如果要从单链列表中删除现有节点cur，可以分两个步骤完成它:

设计链表的实现. 您可以选择使用单链列表或双链列表.

如果要使用双向链表，还需要一个属性prev来指示链表中的上一个节点. 假定链接列表中的所有节点均为0索引.

在链接列表类中实现以下功能:

可能已经提出了使用哈希表的解决方案

所以剩下的问题是: 这两个指针的正确速度应该是多少？

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow.equals(fast)) {
                return true;
            }
        }
        return false;
        
    }
}

给出一个链表，返回到链表中的第一个节点，该节点开始进入环网. 如果链接列表没有铃声，则返回null.

以2.1为基础解决问题，让我们对其进行计算.

QQ屏幕截图20180908102303.png

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow.equals(fast)) {
                break;
            }
        }
        while (head != null && slow != null) {
            if (head.equals(slow)) {
                return slow;
            }
            head = head.next;
            slow = slow.next;
        }
        return null;
    }
}

（要判断它们是否相交，您可以遍历两个链表以查看最后一个节点是否相等）

编写程序以查找两个单独链接的列表相交的起始节点.

例如java 链表，以下两个链接列表:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

交叉点从节点c1开始.

注意:

    /**
     * 返回相交单向链表的交点
     */
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        
        //记录链表的长度
        int lenA = 1;
        ListNode tempA = headA;
        while (tempA.next != null) {
            lenA++;
            tempA = tempA.next;
        }
        int lenB = 1;
        ListNode tempB = headB;
        while (tempB.next != null) {
            lenB++;
            tempB = tempB.next;
        }
        //判断链表是否相交，不想交直接返回null
        if (!tempA.equals(tempB)) {
            return null;
        }
        //截取后半段，相同长度的链表
        int reduseCount = lenA - lenB;
        tempA = headA;
        tempB = headB;
        if (reduseCount > 0) {
            for (int i = 0; i < reduseCount; i++) {
                tempA = tempA.next;
            }
        } else {
            reduseCount = Math.abs(reduseCount);
            for (int i = 0; i < reduseCount; i++) {
                tempB = tempB.next;
            }
        }
        //循环遍历找到交点
        while (tempB != null && tempA != null) {
            if (tempB.equals(tempA)) {
                return tempB;
            }
            tempA = tempA.next;
            tempB = tempB.next;
        }
        return null;
    }

给出链表，删除链表的倒数第二个节点，然后返回链表的头节点.

示例:

给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.

    /**
     * 删除链表的倒数第 n 个节点
     */
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return null;
        }
        if (n == 0) {
            return null;
        }
        ListNode first = head;
        ListNode sec = head;
        for (int i = 0; i < n; i++) {
            first = first.next;
        }
        while (first != null && first.next != null) {
            first = first.next;
            sec = sec.next;
        }
        if (sec.next == null) {
            return null;
        }
        sec.next = sec.next.next;
        return head;
    }

仔细定义循环的结束条件.

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

示例:

输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5

代码

    /**
     * 删除链表中的节点
     */
    public static ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        //定义前指针 是为了删除节点
        ListNode pre = null;
        
        //定义next是为了指针后移
        ListNode next;
        
        for (ListNode i = head; i != null; i = next) {
            next = i.next;
            if (i.val == val) {
                //这个判断说明头一个节点，就需要删除，因此头指针后移
                if (head.equals(i)) {
                    head = head.next;
                }
                //前节点next指向后节点
                if (pre != null) {
                    pre.next = i.next;
                }
                i.next = null;
            } else {
                pre = i;
            }
        }
        return head;
    }

输入: 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

说明:

    public static ListNode oddEvenList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode odd = head;
        ListNode even = head.next;
        ListNode evenHead = head.next;
        while (odd.next != null && even.next != null) {
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }

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