算法之链表

链表

160. 相交链表

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

解法

设 A 的长度为 a + c，B 的长度为 b + c，其中 c 为尾部公共部分长度，可知 a + c + b = b + c + a。
当访问 A 链表的指针访问到链表尾部时，令它从链表 B 的头部开始访问链表 B；同样地，当访问 B 链表的指针访问
到链表尾部时，令它从链表 A 的头部开始访问链表 A。这样就能控制访问 A 和 B 两个链表的指针能同时访问到交
点 .

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

    //这道题的意思是必定有相交的
    ListNode curA=headA;
    ListNode curB=headB;
    while (curA!=curB){
        curA=(curA==null)?headB:curA.next;
        curB=(curB==null)?headA:curB.next;
    }
    return curA;

}

206. 反转链表

反转一个单链表。

示例:

1 2	输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

leetcode原题地址

解法

递归解法

public ListNode reverseList(ListNode head) {
    if(head==null||head.next==null){
        return head;
    }
    ListNode next=head.next;
    //反转 1->2->3 就可以看成 反转（2->3）+1
    ListNode node = reverseList(head.next);
    //next.next就是反转后的链表的尾节点
    next.next=head;
    //head是两个链表合并后的最后一个节点，因此heae.next需要设置尾null
    head.next=null;
    return node;

}

头插法

public ListNode reverseList(ListNode head) {
      ListNode tmpHead=new ListNode(0);
      while (head!=null){
          ListNode next=head.next;
          head.next=tmpHead.next;
          tmpHead.next=head;
          head=next;
      }
      return  tmpHead.next;

   }

直接反转法

public ListNode reverseList(ListNode head) {
     ListNode pre=null;
     ListNode cur=head;
     ListNode next=null;
     while (cur!=null){
         next=cur.next;
         //反转
         cur.next=pre;
         //pre后移
         pre=cur;
         //后移
         cur=next;

     }
     return pre;

   }

21. 合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

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

leetcode原题地址

解法


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

}

以上是递归解法，也可以使用非递归。

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

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 1:

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

示例 2:

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

leetcode原题地址

解法

public ListNode deleteDuplicates(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        head.next=deleteDuplicates(head.next);
        return head.val==head.next.val?head.next:head;

    }

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

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

示例：

1
2
3

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

leetcode原题地址

解法

public ListNode removeNthFromEnd(ListNode head, int n) {

       ListNode fast=head;
       ListNode slow=head;
       for(int i=0;i<n;i++){
           fast=fast.next;
       }
       if(fast==null){
           return head;
       }
       while (fast.next!=null){
           fast=fast.next;
           slow=slow.next;
       }

       slow.next=slow.next.next;
       return head;

   }

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

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

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

示例:

1	给定 1->2->3->4, 你应该返回 2->1->4->3.

leetcode原题地址

解法

public ListNode swapPairs(ListNode head) {
       ListNode node = new ListNode(-1);
       node.next = head;
       ListNode pre = node;
       while (pre.next != null && pre.next.next != null) {
           ListNode l1 = pre.next, l2 = pre.next.next;
           ListNode next = l2.next;
           l1.next = next;
           l2.next = l1;
           pre.next = l2;pre = l1;
       } 
       return node.next;
   }

445. 两数相加Ⅱ

给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

进阶:

如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

示例:

1 2	输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) 输出: 7 -> 8 -> 0 -> 7

leetcode原题地址

解法

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

       Stack<Integer> stackA = buildStack(l1);
       Stack<Integer> stackB = buildStack(l2);
       ListNode tmpHead=new ListNode(-1);
       int carry=0;
       while (!stackA.isEmpty()||!stackB.isEmpty()||carry!=0){

            int A =stackA.isEmpty()?0: stackA.pop();
            int B =stackB.isEmpty()?0: stackB.pop();
            ListNode node = new ListNode((A + B+carry) % 10);

            carry=(A+B+carry)/10;
            node.next=tmpHead.next;
            tmpHead.next=node;

       }
       return tmpHead.next;

   }


   private Stack<Integer> buildStack(ListNode head){
       Stack<Integer> stack = new Stack<>();
       while (head!=null){
           stack.push(head.val);
           head=head.next;
       }
       return stack;
   }

725. 分隔链表

给定一个头结点为 root 的链表, 编写一个函数以将链表分隔为 k 个连续的部分。

每部分的长度应该尽可能的相等: 任意两部分的长度差距不能超过 1，也就是说可能有些部分为 null。

这k个部分应该按照在链表中出现的顺序进行输出，并且排在前面的部分的长度应该大于或等于后面的长度。

返回一个符合上述规则的链表的列表。

举例： 1->2->3->4, k = 5 // 5 结果 [ [1], [2], [3], [4], null ]

示例 1：

输入: 
root = [1, 2, 3], k = 5
输出: [[1],[2],[3],[],[]]
解释:
输入输出各部分都应该是链表，而不是数组。
例如, 输入的结点 root 的 val= 1, root.next.val = 2, \root.next.next.val = 3, 且 root.next.next.next = null。
第一个输出 output[0] 是 output[0].val = 1, output[0].next = null。
最后一个元素 output[4] 为 null, 它代表了最后一个部分为空链表。

示例 2：

输入: 
root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
输出: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
解释:
输入被分成了几个连续的部分，并且每部分的长度相差不超过1.前面部分的长度大于等于后面部分的长度。

提示:

root 的长度范围： [0, 1000].
输入的每个节点的大小范围：[0, 999].
k 的取值范围： [1, 50].

leetcode原题地址

解法

public ListNode[] splitListToParts(ListNode root, int k) {
        int N = 0;
        ListNode cur = root;
        while (cur != null) {N++;
            cur = cur.next;
        } 
        int mod = N % k;
        int size = N / k;
        ListNode[] ret = new ListNode[k];
        cur = root;
        for (int i = 0; cur != null && i < k; i++) {
            ret[i] = cur;
            int curSize = size + (mod-- > 0 ? 1 : 0);
            for (int j = 0; j < curSize - 1; j++) {
                cur = cur.next;
            }
            ListNode next = cur.next;
            cur.next = null;
            cur = next;
        } 
        return ret;
    }