LC-链表专题(一)

2 两数相加【中】

思路：先获取两个链表的长度，以较长的的作为遍历次数。新建一个链表存储结果，每次循环将对应的位的数相加，同时设置一个标志位记录本次加法是否进位。若有进位则下一次的加法要+1

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
 public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummyHead = new ListNode(0);
    ListNode p = l1, q = l2, curr = dummyHead;
    int carry = 0;
    while (p != null || q != null) {
        int x = (p != null) ? p.val : 0;
        int y = (q != null) ? q.val : 0;
        int sum = carry + x + y;
        carry = sum / 10;
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
        if (p != null) p = p.next;
        if (q != null) q = q.next;
    }
    if (carry > 0) {
        curr.next = new ListNode(carry);
    }
    return dummyHead.next;
}

改进：

无需遍历获得长度，当两结点均为null时终止循环即可
注意不要遗漏最后的一次进位
使用dummyHead结点保存结果链表的起始位置，用于返回最终结果 dummyHead.next
Java中新建值为x的链表结点new ListNode(x) 下一结点Cur.next —不用指针真方便啊

时间和空间复杂度：$O(max(m,n))$

19 删除链表的倒数第N个节点【中】

思路:双指针差距为n，同时向后移动，当后面那个指针指向null时，前一个指针所指的即为要删除的结点。要返回链表的头结点，还要设一个指针存储头结点位置。—快慢指针

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {    
        ListNode pre = new ListNode(0);
        pre.next = head;
        ListNode start = pre, end = pre;
        while(n != 0) {
            start = start.next;
            n--;
        }
        while(start.next != null) {
            start = start.next;
            end = end.next;
        }
        end.next = end.next.next;
        return pre.next;
    }
}

改进：

为了方便处理head被删除的特殊情况，添加一个pre/dummyHead结点，使pre.next = head
因为删除时要知道前一结点，故判断条件为start.next=null时终止，此时end正好位于倒数n+1的位置
Java的删除end.next = end.next.next; 因为有垃圾回收机制，无需手动free

时间复杂度：$O(n)$

21 合并两个有序链表【易】

思路：取下两个链表中较小的头结点挂到新链表的末尾，当其中一个链表为空时将另一个链表的剩余部分整体挂上。注意新链表是直接利用原链表中的结点，没有新建。

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);
        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }
        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
##     }
}

改进：

prev.next = l1 == null ? l2 : l1;此句简单精妙

最好时间复杂度：$O(min(m,n))$
最坏时间复杂度：$O(m+n)$

递归法:
两个链表头部较小的一个与剩下元素的 merge 操作结果合并。如果 l1 或者 l2 一开始就是 null ，那么没有任何操作需要合并，所以我们只需要返回非空链表。如果两个链表都是空的，那么过程终止—递归就是简洁

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        else if (l2 == null) {
            return l1;
        }
        else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }
        else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }

    }
}

时间和空间复杂度：$O(m+n)$

23 合并K个有序链表【难】

思路: k路归并的具体实现，不太清楚，难道是堆排序?建一个K个结点的小根堆

public ListNode mergeKLists(ListNode[] lists) {
       int len = 0;
       if((len=lists.length)==0 || lists == null) return null;
       ListNode preHead = new ListNode(-1);
       ListNode preNode = preHead;
       PriorityQueue<ListNode> queue = new PriorityQueue<>(len, new Comparator<ListNode>() {
           @Override
           public int compare(ListNode o1, ListNode o2) {
               return o1.val - o2.val;
           }
       });
       for (ListNode node : lists) {
           if(node!=null) queue.add(node);
       }
       while(!queue.isEmpty()){
           ListNode small = queue.poll();
           preNode.next = small;
           if(small.next!=null) queue.add(small.next); //将最小值节点后面的节点添加到队里中
           preNode = preNode.next;
       }
       return preHead.next;
   }

改进：

用优先队列来代替小根堆，要重写比较器
每次要加入的新结点取自 small.next
ListNode node : lists 遍历每个链表的头结点?

时间复杂度：$O(n*(log(k))$
空间复杂度：$O(k)$

分治法：
两两归并，关键在于用二分法确定分组。归并法用上一题的递归

class Solution {
   public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        return merge(lists, 0, lists.length - 1);
    }

    private ListNode merge(ListNode[] lists, int left, int right) {
        if (left == right) return lists[left];
        int mid = left + (right - left) / 2;
        ListNode l1 = merge(lists, left, mid);
        ListNode l2 = merge(lists, mid + 1, right);
        return mergeTwoLists(l1, l2);
    }

    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1,l2.next);
            return l2;
        }
    }
}

时间复杂度：$O(n*(log(k))$
空间复杂度：$O(n)$

24 两两交换链表中的节点【中】

思路：第一反应是换值，结果被重点强调了..应该是以某种方式去改变指针指向，注意防止断链。可以想到的做法是：

新建一个额外的结点便于操作头结点。

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode pre = new ListNode(0);
        pre.next = head;
        ListNode temp = pre;
        while(temp.next != null && temp.next.next != null) {
            ListNode start = temp.next;
            ListNode end = temp.next.next;
            temp.next = end;
            start.next = end.next;
            end.next = start;
            temp = start;
        }
        return pre.next;
    }
}

改进:

三个指针，更好理解

递归法
返回值：交换完成的子链表
调用单元：设需要交换的两个点为 head 和 next，head 连接后面交换完成的子链表，next 连接 head，完成交换
终止条件：head 为空指针或者 next 为空指针，也就是当前无节点或者只有一个节点，无法进行交换

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;
    }
}

25 K个一组翻转链表【难】

思路：其实跟上题还是同样的原理，只是指针指向要根据k值作相应的调整。最后一组若第一次指针操作发现将指向null，则将此组保持原样。

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;

    ListNode pre = dummy;
    ListNode end = dummy;

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

        end = pre;
    }
    return dummy.next;
}

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

改进:

分段进行，模块化重复；将中间逆序后再将首尾相接
end.next = null;先把尾部置空。 pre.next = reverse(start);然后对首部调用逆序函数
逆序函数的实现，需要三个指针

61 旋转链表【中】

思路：先遍历找到尾结点，然后将前k%list.length个结点依次插入到尾部—然后发现我理解错了题意…能不能连成一个环，然后从中间剪断..

class Solution {
  public ListNode rotateRight(ListNode head, int k) {
    // base cases
    if (head == null) return null;
    if (head.next == null) return head;

    // close the linked list into the ring
    ListNode old_tail = head;
    for(int n = 1; old_tail.next != null; n++)
      old_tail = old_tail.next;
    old_tail.next = head;

    // find new tail : (n - k % n - 1)th node
    // and new head : (n - k % n)th node
    ListNode new_tail = head;
    for (int i = 0; i < n - k % n - 1; i++)
      new_tail = new_tail.next;
    ListNode new_head = new_tail.next;

    // break the ring
    new_tail.next = null;

    return new_head;
  }
}

改进：

新的表头在 n-k%n 处，表尾在表头的前一位置

时间复杂度：$O(n)$
空间复杂度：$O(1)$

83 删除排序链表中的重复元素【易】

思路: 由于是排序的所以排序遍历，设定一个比较位，后面的值与该数相等时，删除，不过由于可能有多个连续的相同数，故没有必要一个个删，可以找到一个更大的数后一起删除，同时更新比较位

class Solution {
    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;
    }
}

此算法依然是挨个删除的，数据较少时区别不大。

时间复杂度：$O(n)$
空间复杂度：$O(1)$

82 删除排序链表中的重复元素 ll【中】

思路：相比于上一题的区别在于把重复的数本身也删除了。看来要在前面加多一个指针?

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = dummy;
        while (cur.next != null && cur.next.next != null) {
            if (cur.next.val == cur.next.next.val) {
                ListNode temp = cur.next;
                while (temp != null && temp.next != null && temp.val == temp.next.val ) {
                    temp = temp.next;
                }
                cur.next = temp.next;
            } 
            else
                cur = cur.next;
        }
        return dummy.next;
    }
}

改进:

因为head结点可能要被删除，故应新增一个结点，而不仅仅是增加一个指针。
在迭代过程中，如果cur.next.val == cur.next.next.val说明此时有重复元素，此时创建一个临时指针temp，指向cur的下一个节点，即temp指向的第一个重复元素所在的位置。通过while循环去重，去重后，temp指向的是重复元素中的最后一个位置。最后cur.next = temp.next就实现了消除重复元素。
相比于上一题，把cur = cur.next;放在else中后判断，即可实现有多个相同值时一起删除，妙啊！
注意退出条件 cur.next != null && cur.next.next != null

时间复杂度：$O(n)$
空间复杂度：$O(1)$

递归法

public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return head;
        }

        if (head.next != null && head.val == head.next.val) {
            while (head != null && head.next != null && head.val == head.next.val) {
                head = head.next;
            }
            //去掉所有重复的数字，然后进行递归
            return deleteDuplicates(head.next);
        } else {
            head.next = deleteDuplicates(head.next);
        }
        return head;
    }

无需dummy结点
对于前面的部分，直接把重复的部分掐掉，剩下的部分递归