算法题-链表

//链表结点定义
  public class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { val = x; }
  }

206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

思路：使用递归，那么递归到最后一个数就到了返回栈栈顶，然后依次退栈，退栈返回的是栈顶的结点，翻转相邻的两个节点即可

//迭代
public ListNode reverseList(ListNode head) {
  ListNode pre = null;
      while(head != null){
          ListNode t = head.next;
          head.next = pre;
          pre = head;
          head = t;
      }
      return pre;
}

//递归
public ListNode reverseList(ListNode cur) {
    if(cur == null || cur.next == null) return cur;
       ListNode p =  reverseList(cur.next);
        cur.next.next = cur;
        cur.next = null;
        return p;
}

160. 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

思路：先分别找到两个链表各自的长度，然后计算长度差，然后让长的链表先走差值个步数，然后再一起走，当他们相遇的时候就是相交的结点。注意特殊情况，1）第一个结点就相交，直接返回 ，2）同步走的时候判断当前结点是否相等，而不是下一个

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
      if(headB ==headA) return headA;
      int sizeA = 0;
      int sizeB = 0;
      ListNode a = headA;
      while(a != null){
          sizeA++;
          a = a.next;
      }  

      ListNode b = headB;
      while(b != null){
          sizeB++;
          b = b.next;
      }

      ListNode longer = null;
      ListNode shorter = null;
      int x = 0;
      if(sizeA > sizeB){
          longer = headA;
          shorter = headB;
          x = sizeA -sizeB;
      }else {
          longer = headB;
          shorter = headA;
          x = sizeB -sizeA;
      }

      while(x > 0){
          x--;
          longer = longer.next;
      }
      while(longer != null){
          if(longer == shorter) {//先判断是否相等，然后再遍历之后的
              return longer;
          }
          longer = longer.next;
          shorter = shorter.next;
      }
      return null;
    }
}

61. 旋转链表

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

示例 1:
输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL

示例 2:
输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL

思路：模拟这个过程，先得到链表长度，%运算得到切分点，移动到切分结点的前一个结点，切分链表，重新拼接

public ListNode rotateRight(ListNode head, int k) {
       if(head == null) return null;
       int len = 0;
       ListNode r = head;
       //得到长度
       while(r != null){
           len++;
           r = r.next;
       }
       //计算向右移动步数
       k = k % len;
       if(k == 0) return head;
       ListNode m = head;
       //计算切分点的上一个结点
       int i = len - k-1;
       ListNode front = head;
       while(i > 0){
           front = front.next;
           i--;
       }
       //拿到尾结点
       ListNode tail = front;
       while(tail.next != null){
           tail = tail.next;
       }
       tail.next = head;

       ListNode newHead = front.next;
       front.next = null;
       return newHead;
   }

142. 环形链表 II

给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

思路：采用快慢指针判断是否有环，如果有那么遍历一遍环得到它的大小，然后从头采用头尾指针的方法，让头指针先走环大小个结点，然后再让头、尾指针同步移动，当它们相遇的时候就是入口结点

public ListNode detectCycle(ListNode head) {
    if(head == null) return null;
       ListNode fast = head.next;
       ListNode slow = head;
       while (fast != null && fast.next != null) {
           fast = fast.next.next;
           slow = slow.next;
           if (fast == slow) {
               break;
           }
       }
       //如果快指针是null，说明没环
       if (fast == null || fast.next==null) return null;

       //得到环的大小
       int c = 1;
       ListNode node = fast.next;
       while (node != fast) {
           node = node.next;
           c++;
       }

       //让头指针先走环的大小步
       ListNode front = head;
       while (c-- > 0) {
           front = front.next;
       }

       //头尾指针一起走，一定会相遇，第一次相遇就是入口结点
       ListNode tail = head;
       while (front != tail) {
           tail = tail.next;
           front = front.next;
       }
       return tail;
   }

143. 重排链表

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

思路：1、快慢指针找到中间结点 ，分成左右两部分 2、翻转得到的右链表 3、左右链表依次拿一个结点组成新的链表

public void reorderList(ListNode head) {
    if (head == null) return;
    ListNode fast = head.next;
    ListNode slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    ListNode l2 = slow.next;
    //左链表末尾置null
    slow.next = null;

    ListNode head2 = reverse(l2);

    ListNode p1 = head;
    ListNode p2 = head2;
    //重新拼接链表
    while (p1 != null && p2 != null) {
        ListNode t = p1.next;
        ListNode t2 = p2.next;
        p1.next = p2;
        p2.next = t;
        p1 = t;
        p2 = t2;
    }
}

private ListNode reverse(ListNode node) {
    ListNode preNode = null;
    while (node != null) {
        ListNode t = node.next;
        node.next = preNode;
        preNode = node;
        node = t;
    }
    return preNode;
}

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

题目描述
将给定的链表中每两个相邻的节点交换一次，返回链表的头指针
例如:
给出1->2->3->4，你应该返回链表2->1->4->3。

思路：构建一个头指针，指向要交换结点的第一个结点，这样方便遍历，然后模拟交换就行

public ListNode swapPairs(ListNode head) {
            if(head == null || head.next ==null) return head;
            ListNode preNode = new ListNode(-1);
            ListNode returnHead = null;
            preNode.next = head;
            while(preNode != null && preNode.next != null){
                ListNode p1 = preNode.next;
                ListNode p2 = preNode.next.next;
                if(p2 == null){//如果第二个结点为空，说明总结点个数是奇数，并且到末尾了，直接退出
                    break;
                }
                ListNode n = p2.next;
                preNode.next = p2;
                p2.next = p1;
                p1.next = n;
                if(returnHead == null){//第一次赋值就是头结点
                    returnHead = p2;
                }
                preNode = preNode.next.next;
            }
            return returnHead;
    }

148. 排序链表

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

思路：归并排序，使用快慢指针找到二分点，并将slow.next置空，防止merge出错，再使用merge归并左右两个链表

public ListNode sortList(ListNode head) {
       if (head == null || head.next == null) return head;
       ListNode fast = head.next;
       ListNode slow = head;
       while (fast != null && fast.next != null) {
           fast = fast.next.next;
           slow = slow.next;
       }
       ListNode t = slow.next;
       slow.next = null;
       ListNode left = sortList(head);
       ListNode right = sortList(t);
       return merge(left, right);
   }


   private ListNode merge(ListNode a, ListNode b) {
       if (a == null) return b;
       if (b == null) return a;
       if (a.val < b.val) {
           a.next = merge(a.next, b);
           return a;
       }
       b.next = merge(a, b.next);
       return b;
   }

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

题目描述
现在有一个这样的链表：链表的每一个节点都附加了一个随机指针，随机指针可能指向链表中的任意一个节点或者指向空。
请对这个链表进行深拷贝。

思路：三次遍历，
第一次遍历：将拷贝的结点依次插入被拷贝结点的下一个，形成一个混合的链表。
第二次遍历：将被拷贝结点的random指向拷贝结点的random的下一个
第三次遍历：最后分离这两个链表。

public RandomListNode copyRandomList(RandomListNode head) {

        //新建结点
        RandomListNode cur = head;
        while (cur != null) {
            RandomListNode node = new RandomListNode(cur.label);
            node.next = cur.next;
            cur.next = node;
            cur = node.next;
        }

        //新建结点的random指针赋值
        cur = head;
        while (cur != null && cur.next != null) {
            if (cur.random != null) {
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }

        //分离
        cur = head;
        RandomListNode dummy = new RandomListNode(-1);
        RandomListNode newHead = dummy;
        while (cur != null) {
            newHead.next = cur.next;
            newHead = newHead.next;
            cur.next = cur.next.next;
            cur = cur.next;
        }
        return dummy.next;
    }

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

给定一个链表，删除链表的倒数第n个节点并返回链表的头指针
例如，
给出的链表为:1->2->3->4->5, n= 2.

删除了链表的倒数第n个节点之后,链表变为1->2->3->5.

思路：一次完成，一个技巧是使用dummy开头，这样可以很方便计算移动的次数，比如找倒数第二个，那么wile循环2次就可以找到这个结点的上一个结点

public ListNode removeNthFromEnd(ListNode head, int n) {
       ListNode dummy = new ListNode(-1);
       dummy.next = head;
       ListNode a = dummy;
       while (n > 0) {
           a = a.next;
           n--;
       }
       ListNode b = dummy;
       while (a.next != null) {
           b = b.next;
           a = a.next;
       }
       b.next = b.next.next;
       return dummy.next;

   }

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

删除给出链表中的重复元素，使链表中的所有元素都只出现一次
例如：
给出的链表为1->1->2,返回1->2.
给出的链表为1->1->2->3->3,返回1->2->3.

思路：使用头尾指针，头指针指向下一个比较的结点，尾指针指向排好序的链表的尾。比较的是头尾指针的值

public ListNode deleteDuplicates(ListNode head) {
       if (head == null) {
           return null;
       }
       ListNode fast = head.next, slow = head;
       while (fast != null) {
           if (fast.val == slow.val) {
               fast = fast.next;
           } else {
               slow.next = fast;
               fast = fast.next;
               slow = slow.next;
           }
       }
       slow.next = null;
       return head;
   }

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

给出一个排好序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。
例如：
给出的链表为1->2->3->3->4->4->5, 返回1->2->5.
给出的链表为1->1->1->2->3, 返回2->3.

思路：和删除排序链表中的重复元素类似，但是需要一个哑头结点避免删除头结点的情况

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

       ListNode dummy = new ListNode(0, head);

       ListNode cur = dummy;
       while (cur.next != null && cur.next.next != null) {
           if (cur.next.val == cur.next.next.val) {
               int x = cur.next.val;
               while (cur.next != null && cur.next.val == x) {
                   cur.next = cur.next.next;
               }
           } else {
               cur = cur.next;
           }
       }

       return dummy.next;
   }

86. 分隔链表

给出一个链表和一个值x，以x为参照将链表划分成两部分，使所有小于x的节点都位于大于或等于x的节点之前。
两个部分之内的节点之间要保持的原始相对顺序。
例如：
给出1->4->3->2->5->2和x = 3,
返回1->2->2->4->3->5.

思路：用快慢指针，快指针指向需要比较的结点的前一个，慢指针指向比值小的链表尾，每次快指针发现下一个结点比x小那就将这个结点插入到slow之后

public ListNode partition(ListNode head, int x) {

       ListNode dummy = new ListNode(-1);
       dummy.next = head;
       ListNode fast = dummy, slow = dummy;

       while (fast != null && fast.next != null) {
           if (fast.next.val >= x) {//比x大，直接下一个
               fast = fast.next;
           } else {//小于的情况
               if (fast == slow) {
                   fast = fast.next;
                   slow = slow.next;
               } else {
                   ListNode temp = fast.next;
                   fast.next = temp.next;
                   temp.next = slow.next;
                   slow.next = temp;
                   slow = slow.next;
               }
           }
       }
       return dummy.next;
   }

92. 反转链表 II

将一个链表m位置到n位置之间的区间反转，要求使用原地算法，并且在一次扫描之内完成反转。
例如：
给出的链表为1->2->3->4->5->NULL, m = 2 ，n = 4,
返回1->4->3->2->5->NULL.
注意：
给出的m，n满足以下条件：
1 ≤ m ≤ n ≤ 链表长度

思路：模拟，这种一定会会有一个dummy head才行

public ListNode reverseBetween(ListNode head, int m, int n) {
     ListNode dummy = new ListNode(0);
     dummy.next = head;
     ListNode preStart = dummy;//代表翻转链表之前的那个结点
     ListNode start = head;//翻转的起始结点
     for (int i = 1; i < m; i ++ ) {//找到翻转链表的起始位置
         preStart = start;
         start = start.next;
     }
     // reverse
     for (int i = 0; i < n - m; i ++ ) {//翻转
         ListNode temp = start.next;//下一个结点
         start.next = temp.next;
         temp.next = preStart.next;
         preStart.next = temp;
     }
     return dummy.next;
 }

面试题 02.05. 链表求和

给定两个用链表表示的整数，每个节点包含一个数位。
这些数位是反向存放的，也就是个位排在链表首部。
编写函数对这两个整数求和，并用链表形式返回结果。
示例：
输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
输出：2 -> 1 -> 9，即912

思路：
（1）不要想着直接在这个两个链表之间使用一个指针遍历所有
（2）结果直接新建一个链表，头结点只是一个引导，之后的链表才是结果
（3）基本的思想就是，遍历的次数是最长的链表长度，如果其中一个链表结点遍历完了，那么就假设他是0
carry记得置0

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode p1 = l1, p2 = l2;
    ListNode result = new ListNode(0);
    ListNode head = result;
    int carry = 0;
    while (true) {
        int a, b;
        if (p1 == null) {
            a = 0;
        } else {
            a = p1.val;
        }

        if (p2 == null) {
            b = 0;
        } else {
            b = p2.val;
        }
        int val = a + b + carry;
        if (val < 9) {
            carry = 0;
        } else {
            carry = val / 10;
            val = val % 10;
        }

        result.next = new ListNode(val);
        result = result.next;

        if (p1 != null)
            p1 = p1.next;

        if (p2 != null)
            p2 = p2.next;

        if (p1 == null && p2 == null) {
            break;
        }

    }

    if (carry > 0) {
        result.next = new ListNode(carry);
    }
    return head.next;
}

21. 合并两个有序链表

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

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
           if(list1 == null) return list2;
           if(list2 == null) return list1;
           if(list1.val < list2.val){
               list1.next = mergeTwoLists(list1.next,list2);
               return list1;
           }else {
               list2.next = mergeTwoLists(list1,list2.next);
               return list2;
           }
   }

109. 有序链表转换二叉搜索树

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定的有序链表： [-10, -3, 0, 5, 9],

一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

  0
 / \

-3 9
/ /
-10 5

思路：快慢指针找到中间结点，注意不必找到第一次的尾链表结点作为边界，直接用null作为边界，然后创建TreeNode，左子树再从左链表构建，右子树同理

public TreeNode sortedListToBST(ListNode head) {
          return sortedListToBST(head,null);
     }
  public TreeNode sortedListToBST(ListNode start,ListNode end) {
          if(start == end) return null;
          ListNode middle = middleNode(start,end);
          TreeNode root = new TreeNode(middle.val);
          root.left = sortedListToBST(start,middle);
          root.right = sortedListToBST(middle.next,end);
          return root;
  }

  ListNode middleNode(ListNode start,ListNode end){
      ListNode fast = start,slow = start;

      while(fast != end && fast.next != end ){//fast.next != end 类比于 找一次中间结点时fast.next == null
          fast = fast.next.next;
          slow = slow.next;
      }
      return slow;
  }

147. 对链表进行插入排序

给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。
思路：插入一定要引入dummyNode，dummyNode和第一个结点作为被插入的列表，由此和剩余结点断开，避免指针错误，每操作一个结点都应该注意把它指针置为null
将整个过程分解：
1）插入结点的方法
2）从头寻找插入结点的方法
3）遍历需要插入的结点的方法

public ListNode insertionSortList(ListNode head) {

      ListNode dummyNode = new ListNode(-1);
      dummyNode.next = head;
      ListNode curNode = head.next;
      head.next = null;
      while (curNode != null) {
          ListNode nextNode = curNode.next;
          curNode.next = null;
          insert(dummyNode, curNode);
          curNode = nextNode;
      }
      return dummyNode.next;

  }

  void insertNode(ListNode preNode, ListNode insertNode) {
      ListNode t = preNode.next;
      preNode.next = insertNode;
      insertNode.next = t;
  }

  void insert(ListNode dummyNode, ListNode insertedNode) {
      ListNode cur = dummyNode.next;
      ListNode preNode = dummyNode;
      while (cur != null && cur.val < insertedNode.val) {
          cur = cur.next;
          preNode = preNode.next;
      }
      insertNode(preNode, insertedNode);
  }