未命名分组 - 链表 - 《数据结构 · Leetcode · SQL · 刷题笔记》

328. 奇偶链表

思路2（更好）：使用一个奇指针，一个偶数指针，奇数的吧奇数的都串起来，偶数的吧偶数的都串起来，记录一下偶数的头，最后把奇数的尾巴和偶数的头连接起来就好了。

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

思路1：一个一个节点换过来,需要警惕的就是边界的条件，这个next指针可能会为空。

class Solution {
    public ListNode oddEvenList(ListNode head) {
        ListNode p = head;
        if(head == null){
            return head;
        }
        ListNode odd_head = head.next;
        ListNode odd_end = odd_head;
        if(odd_end==null||odd_end.next==null){
            return head;
        }
        ListNode q = odd_end.next;
        while (q!=null){
            if(q.next!=null){
                ListNode next = q.next;
                p.next = q;
                q.next = odd_head;
                odd_end.next = next;
                odd_end = odd_end.next;
                p = p.next;
                q = odd_end.next;
            }else {
                p.next = q;
                q.next = odd_head;
                odd_end.next = null;
                odd_end = odd_end.next;
                p = p.next;
                q = null;
            }
        }
        return head;
    }
}

面试题 02.01. 移除重复节点

思路一：
使用HashSet来做一个记录，同时记录一下前置的节点和当前的节点。一旦发现有重复的数值，直接修改next 指针，指向下一个元素。

class Solution {
    public ListNode removeDuplicateNodes(ListNode head) {
        HashSet<Integer> set = new HashSet<>();
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode node = head;
        ListNode pre = dummyHead;
        while (node!=null){
            if(set.contains(node.val)){
               pre.next = node.next;
               node = node.next;
                continue;
            }
            set.add(node.val);
            pre = node;
            node = node.next;
        }
        return dummyHead.next;
    }
}

2. 两数相加

记录一下进位，然后里面的一个小技巧就是
int val1 = l1==null?0:l1.val;
这样就不用把链表哪个先空给考虑进去。

注意链表的位置，什么时候是边界条件，什么时候循环退出？
对于这题来说，只有两个链表都为空的时候才会退出，但边界的时候可以置0跳过，最后需要注意最后一位进位时，已经跳出循环了，需要补充一下。

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode node = dummyHead;
        int carry=0;
        while (l1!=null||l2!=null){
            int val1 = l1==null?0:l1.val;
            int val2 = l2==null?0:l2.val;
            int count = val1+val2+carry;
            carry = count/10;
            count = count%10;
            node.next = new ListNode(count);
            node = node.next;
            if(l1!=null){
                l1 = l1.next;
            }
            if(l2!=null){
                l2 = l2.next;
            }
        }
        if (carry>0){
            node.next = new ListNode(carry);
        }
        return dummyHead.next;
    }
}

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode();
        ListNode res = dummyHead;
        int flag = 0;
        while (l1 != null || l2 != null) {
            int a = l1 == null ? 0 : l1.val;
            int b = l2 == null ? 0 : l2.val;
            int count = a + b + flag;
            flag = count / 10;
            count %= 10;
            res.next = new ListNode(count);
            res = res.next;

            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        if (flag > 0) {
            res.next = new ListNode(flag);
        }
        return dummyHead.next;
    }
}

面试题35. 复杂链表的复制

这道题的链表和以前的不一样，里面有一个回指向任意节点的random节点。
所以我们考虑到分成三部来实现：

复制所有的节点，串联在原先的节点后面。
把random节点叶复制过来。

将一个链表拆分成为两个链表。

/*
// Definition for a Node.
class Node {
 int val;
 Node next;
 Node random;

 public Node(int val) {
     this.val = val;
     this.next = null;
     this.random = null;
 }
}
*/
class Solution {
public Node copyRandomList(Node head) {
     cloneNode(head);
     cloneRandom(head);
     return reconnectNodes(head);

 }
 // 把一个链表分为两个链表
 private Node reconnectNodes(Node head) {
     Node node = head;
     Node cloneHead = null;
     Node cloneNode = null;
     if(node!=null){
         cloneHead = cloneNode = node.next;
         node.next = cloneNode.next;
         node = node.next;
     }
     while (node!=null){
         cloneNode.next = node.next;
         cloneNode = cloneNode.next;
         node.next =cloneNode.next;
         node = node.next;
     }
     return cloneHead;
 }
 // 对这个链表的random也进行复制
 private void cloneRandom(Node head) {
     Node node = head;
     while (node!=null){
         Node next = node.next;
         if(node.random!=null){
             next.random = node.random.next;
         }
         node = next.next;
     }
 }

 //复制这个链表
 private void cloneNode(Node head) {
     Node node = head;
     while (node!=null){
         Node clone = new Node(node.val);
         clone.next = node.next;
         node.next = clone;
         node = clone.next;
     }
 }
}

23. 合并K个排序链表

使用分治的思路去做这个事情。k个链表，我们其实还是可以两个两个去合并在一起。所以后弦我们吧链表进行一个拆分，对半拆分，然后递归调用。 ```java class Solution { public ListNode mergeKLists(ListNode[] lists) {

 if(lists.length==0)return null;
 if(lists.length==1)return lists[0];
 if(lists.length==2)return mergeTwoLists(lists[0],lists[1]);

 int mid = lists.length/2;
 ListNode[] l1 = new ListNode[mid];
 for(int i=0;i<mid;i++){
     l1[i] = lists[i];
 }

 ListNode[] l2 = new ListNode[lists.length-mid];

 for (int i=mid,j=0;i<lists.length;i++){
     l2[j++] = lists[i];
 }
 return mergeTwoLists(mergeKLists(l1),mergeKLists(l2));

}

private ListNode mergeTwoLists(ListNode l1, ListNode l2) {

 if(l1==null) return l2;
 if(l2==null) return l1;

 ListNode dummyhead = new ListNode(0);
 ListNode head = dummyhead;

    while (l1!=null&&l2!=null){
        if(l1.val>l2.val){
            head.next = l2;
            head = head.next;
            l2 = l2.next;
        }else{
            head.next = l1;
            head = head.next;
            l1 = l1.next;
        }
    }
    if(l1!=null){
        head.next = l1;
    }else if(l2!=null){
        head.next = l2;
    }
    return dummyhead.next;

}

}

第二种方法是我们使用一个最小堆来放这个链表。每次都弹出最小的一个，之后把这个节点的后一个加入到里面去。
```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
        if(lists==null)return null;
        if(lists.length==1)return lists[0];

        Queue<ListNode> queue = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode listNode, ListNode t1) {
                return listNode.val-t1.val;
            }
        });

        for (int i=0;i<lists.length;i++){
            if(lists[i] ==null){
                continue;
            }
            queue.add(lists[i]);
        }

        ListNode dummyHead = new ListNode(0);
        ListNode head = dummyHead;

        while (!queue.isEmpty()){
            ListNode tmp = queue.poll();
            head.next = tmp;
            head = head.next;
            if(tmp.next!=null){
                queue.add(tmp.next);
            }
        }
        return dummyHead.next;
    }
}

203-移除链表元素

思路1 不带dummyhead：
首先我们考虑一下头节点是目标的情况。处理之后，判断是否为空。处理剩下的节点。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {

        while(head!=null && head.val == val){
            head = head.next;
        }
        if(head == null){
            return null;
        }
        ListNode pre = head;
        while(pre.next!=null){
            if(pre.next.val == val){
                pre.next = pre.next.next;
            }else{
                pre = pre.next;
            }
        }
        return head;

    }
}

思路2：增加哨兵节点，使用一个dummyHead来指向头结点。这样就不用对头结点进行特殊的优化了。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode pre = dummyHead;
        while(pre.next!=null){
            if(pre.next.val == val){
                pre.next = pre.next.next;
            }else{
                pre = pre.next;
            }
        }
        return dummyHead.next;

    }
}

递归解法：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head == null){
            return null;
        }
        head.next = removeElements(head.next,val);
        return val == head.val?head.next:head;

    }
}

876. 链表的中间结点

返回一个中间节点。需要快慢指针。
快的条件是 fast！null&&fast.next!=null

 public ListNode middleNode(ListNode head) {
        ListNode slow = head,fast=head;
        while (fast!=null&&fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

206. 反转链表

先取得下一个节点，cur开始反转

class Solution {
    public ListNode reverseList(ListNode head) {

        ListNode pre = head;
        ListNode cur = head;
        ListNode reverseNode = null;
        while(pre!=null){
            pre = pre.next;
            cur.next = reverseNode;
            reverseNode = cur;
            cur = pre;

        }
        return reverseNode;



    }
}

递归解法

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

使用递归来做，递归函数的定义是假设这个节点以后的节点都反转好了。

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head== null|| head.next ==null){
            return head;
        }
        ListNode next = head.next;
        head.next = swapPairs(next.next);
        next.next = head;
        return next;


    }
}

方法二：使用循环来做，每次截断两个节点，把这两个节点反转拼合起来。

    public ListNode swapPairs(ListNode head) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;

        ListNode pre = dummyHead;
        ListNode first = dummyHead;
        ListNode sec = dummyHead;
        ListNode next = null;
        while (sec!=null && sec.next!=null){
            sec = sec.next.next;
            first = first.next;
            if(sec!=null){
                next= sec.next;
                sec.next = null;
                pre.next = sec;
                sec.next = first;
                first.next = next;

                pre = first;
                sec = first;
            }


        }
        return dummyHead.next;
    }

141. 环形链表

快慢指针，如果有环的话一定会追上慢指针。

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

        }
        return true;

    }
}

142. 环形链表 II

判断有没有之后需要计算一下环里面的个数。一个指针不动，一个往前走。之后从头开始出发，先走k步，最后会在入口相遇。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null||head.next ==null) return null;
        ListNode fast = head.next;
        ListNode slow = head;

        while(fast!= slow){
            if(fast == null|| fast.next == null){
                return null;
            }
            fast = fast.next.next;
            slow = slow.next;
        }

        int num = 1;
        fast = fast.next;
        while(fast!=slow){
            fast = fast.next;
            num++;
        }
        fast = head;
        slow = head;
        for(int i=0;i<num;i++){
            fast = fast.next;
        }

        while(fast!=slow){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;



    }
}

25. K 个一组翻转链表

依次按k个来翻转。https://leetcode-cn.com/problems/reverse-nodes-in-k-group/solution/tu-jie-kge-yi-zu-fan-zhuan-lian-biao-by-user7208t/

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
      ListNode dummyHead = new ListNode(-1);
         dummyHead.next = head;

         ListNode pre = dummyHead;
         ListNode end = dummyHead;

         while (end.next!=null){
             for(int i=0;i<k&&end!=null;i++) end = end.next;
             if(end == null) break;
             ListNode next = end.next;
             ListNode start = pre.next;
             end.next = null;
             pre.next = reverse(start);
             start.next = next;
             pre = start;
             end = pre;
         }
         return  dummyHead.next;

    }

    private ListNode reverse(ListNode start) {
         ListNode pre = null;
         ListNode curr = start;
         while (curr!=null){
             ListNode next = curr.next;
             curr.next = pre;
             pre = curr;
             curr = next;
         }
         return pre;
    }
}

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

思路：
使用两个指针，一个在前一个在后，遇到相同的数值的时候，快指针就往前走一个。需要注意的是边界条件，while的结束条件是什么？ fast指针不为空，判断两个节点数值的一样时候的边界条件是什么？ fast同样不能为null。

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;
        ListNode fast = head;
        ListNode slow = head;
        if(head == null){
            return head;
        }
        fast = fast.next;
        while(fast!=null){
            while(fast != null && fast.val == slow.val){
                slow.next = fast.next;
                fast = fast.next;
            }
            slow = slow.next;
        }
        return dummyHead.next;
    }
}

优化的思路：
其实我们可以只使用的一个变量来完成整个操作。cur自己的数值和cur.next的数值进行比较，如果是一样的，可以直接调整cur的next指针指向的位置。这里的边界条件是 cur.next!=null

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head== null || head.next == null){
            return head;
        }

        ListNode cur = head;
        while(cur.next!=null){
            if(cur.val == cur.next.val){
                cur.next = cur.next.next;
            }else{
                cur = cur.next;
            }
        }
        return head;
    }
}