leetcode之链表问题

19.删除链表的倒数第N个节点

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

public ListNode removeNthFromEnd(ListNode head, int n) {
    /**
         * 因为要删除某个节点，必须先要获得它的前一个结点
         * 因为有可能删除头节点，所以最好在头节点之前插入一个虚拟头结点
         * 删除倒数第n个节点，需要找到倒数n+1个节点，最后一个节点与倒数n+1个节点相差n个节点
         * 所以，准备first，second两个节点，保证他们距离是n，当second指到尾节点的时候，first恰好指向倒数n+1个节点
         * */

    //虚拟头节点
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode first = dummy;
    ListNode second = dummy;
    for(int i=0;i<n;i++){
        first = first.next;
    }
    while(first.next!=null){
        first = first.next;
        second = second.next;
    }
    second.next = second.next.next;
    return dummy.next;
}

237. 删除链表中的节点

/**
     * 使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。
     * 将该节点的值设置为下一个节点的值，并将下一个节点删除
     * */
public void deleteNode(ListNode node) {
    node.data = node.next.data;
    node.next = node.next.next;
}

83. 删除排序链表中的重复元素

/*
    * 给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
    *
    * 当某个元素与后继元素相等时，直接删除；不等时，指针后移
    * */
public ListNode deleteDuplicates(ListNode head) {
    ListNode cur = head;
    while(cur!=null&&cur.next!=null){
        if(cur.val == cur.next.val){
            cur.next = cur.next.next;
        }else{
            cur = cur.next;
        }
    }
    return head;
}

61.旋转链表

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

public ListNode rotateRight(ListNode head, int k) {
    //尾指针指向头节点，倒数第k+1个节点指向null,头指针指向倒数第k个
    if(head==null){
        return null;
    }
    //求链表长度
    ListNode p =head;
    int n =0;
    while(p!=null){
        n++;
        p=p.next;
    }
    int len = k%n;
    ListNode first = head;
    ListNode second = head;
    for(int i=0;i<len;i++){
        first = first.next;
    }
    while(first.next!=null){
        first = first.next;
        second = second.next;
    }
    first.next = head;
    head =second.next;
    second.next = null;
    return head;
}

24.两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

//需要交换a，b两个节点时
p.next = b
a.next = b.next
b.next = a
p =a

public ListNode swapPairs(ListNode head) {
    //因为头节点也可能会改变，所以需要一个哑节点
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    ListNode cur = dummy;
    while(cur.next!=null&&cur.next.next!=null){
        ListNode a= cur.next;
        ListNode b = a.next;
        cur.next = b;
        a.next = b.next;
        b.next = a;
        cur = a;
    }
    return dummy.next;
}

206.反转链表

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

92.反转链表2

public ListNode reverseBetween(ListNode head, int m, int n) {
    if(head==null){
        return null;
    }
    if(m==n){
        return head;
    }
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    //首先，需要找到prem以及nextn
    ListNode premNode = dummy,nextnNode=dummy;
    for(int i=0;i<m-1;i++){
        premNode = premNode.next;
    }
    for(int i=0;i<n+1;i++){
        nextnNode = nextnNode.next;
    }
    
    
    ListNode pre = premNode;
    ListNode cur = premNode.next;
    ListNode mNode = cur;
    //将m，n之间元素全部反转
    while(cur!=null&&cur!=nextnNode){
        ListNode tmp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = tmp;
    }
    //重新指向
    premNode.next = pre;
    mNode.next = nextnNode;

    return dummy.next;

}

160.相交链表

编写一个程序，找到两个单链表相交的起始节点。

求相交的点，两个指针，第一个指针从a走，走a+c，到达尾部，再从b走；

第二个指针从b走，走b+c，到达尾部，再从a走。

这样，两个指针都走了a+b+c，相交点即为所求。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode first = headA;
    ListNode second = headB;
    while(first!=second){
        if(first!=null){
            first = first.next;
        }else{
            first = headB;
        }

        if(second!=null){
            second = second.next;
        }else{
            second = headA;
        }
    }
    return first;
}

234. 回文链表

/**
     * 遍历链表，将值入栈。
     * 从头遍历链表，将栈顶元素出栈，出栈顺序就是链表元素的逆序元素
     * */
public boolean isPalindrome(ListNode head) {
    Stack<Integer> help = new Stack<>();
    ListNode cur = head;
    //链表元素入栈
    while(cur!=null){
        help.push(cur.val);
        cur = cur.next;
    }
    //从头重新遍历链表，与栈内元素比较，出栈即为链表的逆序
    cur = head;
    while (cur!=null){
        int val = help.pop();
        if(val==cur.val){
            cur = cur.next;
        }else{
            return false;
        }
    }
    return true;
}

空间复杂度为O(1)的方法。

/**
     * 空间复杂度为O(1)的情况。
     * 两个指针，快指针走两步，慢指针走一步。当快指针走完的时候，慢指针刚好走到终点，
     * 从中点开始，往后逆转链表，这样，就会变成1->2->3<-2<-1
     * 这样，两个指针，一个从头开始，一个从尾部开始，遍历链表，直到两者相遇
     * */
public boolean isPalindrome(ListNode head) {
    if(head==null||head.next==null){
        return true;
    }
    ListNode slow = head;
    ListNode fast = head;
    while(fast!=null&&fast.next!=null){
        fast = fast.next.next;
        slow = slow.next;
    }
    //反转链表
    ListNode pre = slow;
    ListNode cur = slow.next;
    slow.next = null;
    while(cur!=null){
        ListNode tmp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = tmp;
    }
    //头尾两个指针遍历
    ListNode first = head;
    ListNode second = pre;
    while(second!=null&&first!=null){
        if(first.val!=second.val){
            return false;
        }else{
            first = first.next;
            second = second.next;
        }
    }
    //将逆转的链表恢复
    ListNode n1 = pre;
    ListNode n2 = pre.next;
    pre.next=null;
    while(n2!=null){
        ListNode tmp = n2.next;
        n2.next = n1;
        n1 = n2;
        n2 = tmp;
    }
    return true;
}

86. 分隔链表

public ListNode partition(ListNode head, int x) {
    if(head==null){
        return null;
    }
    ListNode small = new ListNode(-1);
    ListNode large = new ListNode(-1);
    ListNode small_tail = small;
    ListNode large_tail = large;
    ListNode cur = head;
    while(cur!=null){
        int val = cur.val;
        if(val<x){
            ListNode node = new ListNode(val);
            small_tail.next = node;
            small_tail = node;
        }else{
            ListNode node = new ListNode(val);
            large_tail.next = node;
            large_tail = node;
        }
        cur = cur.next;
    }
    small_tail.next = null;
    large_tail.next =null;
    small_tail.next = large.next;
    return small.next;
}

138. 复制带随机指针的链表

通过哈希表来解决，空间复杂度O(n)

public Node copyRandomList(Node head) {
    if(head==null){
        return null;
    }
    Map<Node,Node> map = new HashMap<>();
    Node cur = head;
    //遍历链表，建立map映射
    while(cur!=null){
        Node copy = new Node(cur.val,null,null);
        map.put(cur,copy);
        cur = cur.next;
    }
    //对链表指针进行拷贝
    cur = head;
    while(cur!=null) {
        if (cur.next != null) {
            map.get(cur).next = map.get(cur.next);
        }
        map.get(cur).random = map.get(cur.random);
        cur = cur.next;
    }
    return map.get(head);
}

空间复杂度为O(1)

/**遍历链表，建立一个包含原节点以及复制节点1->1'->2->2'->3->3'
     * 对复制节点处理random指针
     * 从链表中提取复制节点
     * @param head
     * @return
     */

public Node copyRandomList(Node head) {
    if(head==null){
        return null;
    }
    //1->1'->2->2'->3->3'
    Node cur = head;
    while (cur!=null){
        Node copy = new Node(cur.val,null,null);
        Node tmp = cur.next;
        copy.next = cur.next;
        cur.next = copy;
        cur = tmp;
    }
    //处理random 1' random就是1 random.next.next
    cur = head;
    while(cur!=null){
        cur.next.random =cur.random==null?null:cur.random.next;
        cur = cur.next.next;
    }
    //分离链表
    cur = head;
    Node copyHead = head.next;
    while(cur.next!=null){
        Node tmp = cur.next;
        cur.next = cur.next.next;
        cur = tmp;
    }
    return copyHead;
}

两个链表相交问题

/**
       * 两个可能存在环的链表，需要多种情况讨论：
       *    1.两个链表都没有环，判断相交
       *    2.一个有环，一个没有环，必定不可能相交
       *    3.两个都有环，判断相交
       *    判断是否有环：快慢指针
       *    判断无环链表相交：遍历两个链表，记录长度以及尾部节点，若两个尾部节点不等，不相交；若相等，寻找相交点。
       *        短的链表先走len1-len2步，然后两个链表一起走，两个链表相等的时候就是交点。
       *    判断两个有环链表相交：
       *        分为三种情况：
       *            loop1=loop2，必定有交点，可以转化为无环链表相交问题
       *            loop1!=loop2
       *                相交以及不相交
       *                从链表a的环入点开始走，假如走完一圈没有碰到链表b的环入点，那么就是不相交的。
       * */

public ListNode getIntersectNode(ListNode head1,ListNode head2){
    if(head1==null||head2==null){
        return null;
    }
    ListNode loop1 = detectCycle(head1);
    ListNode loop2 = detectCycle(head2);
    //均没有环，都有环
    if(loop1==null&&loop2==null){
        return bothLoop(head1,head2,loop1,loop2);
    }else if(loop1!=null&&loop2!=null){
        return noLoop(head1,head2);
    }
    //一个有环一个没有环必定不相交
    return null;
}

//两个有环交点的判断
public ListNode bothLoop(ListNode head1,ListNode head2,ListNode loop1,ListNode loop2){
    //假如loop1==loop2，可以看作是尾部节点是loop的两个无环链表相交问题
    if(loop1==loop2){
        ListNode cur1 = head1;
        ListNode cur2 = head2;
        int n=0;
        while (cur1!=loop1){
            n++;
            cur1 = cur1.next;
        }
        while (cur2!=loop2){
            n--;
            cur2 = cur2.next;
        }
        ListNode first = head1;
        ListNode second = head2;
        if(n>0){
            for(int i=0;i<n;i++) {
                first = first.next;
            }
        }else{
            for(int i=0;i<Math.abs(n);i++){
                second = second.next;
            }
        }
        while (first!=second){
            first = first.next;
            second = second.next;
        }
        return first;
    }else{
        //假如loop1!=loo2，从loop1开始走一圈，若有相交点，走这一圈中必定有loop1==loop2
        ListNode cur = loop1.next;
        while(cur!=loop1){
            if(cur==loop2){
                return loop1;
            }else {
                cur = cur.next;
            }
        }
    }
    return null;
}
//无环链表的交点判断
public ListNode noLoop(ListNode head1, ListNode head2) {
    if(head1==null||head2==null){
        return null;
    }
    //获取两个节点的尾部节点以及长度
    ListNode cur1 = head1;
    int length = 0;
    while (cur1.next != null) {
        length++;
        cur1 = cur1.next;
    }
    ListNode cur2 = head2;
    while (cur2.next != null) {
        length--;
        cur2 = cur2.next;
    }
    if (cur1 != cur2) {
        return null;
    }
    //短的先走
    ListNode first = head1;
    ListNode second = head2;
    if (length < 0) {
        for(int i=0;i<Math.abs(length);i++) {
            second = second.next;
        }
    }else{
        for(int i=0;i<length;i++) {
            first = first.next;
        }
    }
    //同时走，寻找相交点
    while (first != second) {
        first = first.next;
        second = second.next;
    }
    return first;
}
/**
       * 寻找环的入口处
       * */
//寻找环的入口点
public ListNode detectCycle(ListNode head) {
    if(head==null){
        return null;
    }
    ListNode interact = getInteract(head);
    if(interact==null){
        return null;
    }
    ListNode first = head;
    ListNode second = interact;
    while(first!=second){
        first = first.next;
        second = second.next;
    }
    return first;
}
//寻找相遇点
public ListNode getInteract(ListNode head){
    ListNode slow = head;
    ListNode fast = head;
    while(fast!=null&&fast.next!=null){
        fast = fast.next.next;
        slow = slow.next;
        if(fast==slow){
            return fast;
        }
    }
    return null;
}

哑节点问题

假如需要操纵节点的前置节点，那么在头节点前面添加一个哑节点。

//跳出while循环，此时cur指向的是最后一个节点
while(cur.next!=null){
}