leetcode_链表

发表于 2018-07-22 | 更新于 2018-09-22 | 分类于 leetcode

链表

1、链表是否有环（141. Linked List Cycle）

// 快慢节点，快的一次走两步，慢的一次走一步，快的始终比慢的快，当两者相等的时候，说明有环
public boolean hasCycle(ListNode head) {
    if(head == null) return false;
    ListNode fast = head;
    ListNode slow = head;
    while(fast.next != null){
        fast = fast.next;    //走两步
        if(fast.next == null){
            return false;
        }
        fast = fast.next;
        slow = slow.next;    // 走一步
        
        if(fast == slow){
            return true;
        }
    }
    return false;
}

2、链表环的入口（142. Linked List Cycle II）

// 只要证明相等的时候，从head走到入口和fast继续走到入口的距离相等
// 第一次相遇的时候： S_fast = |OA| + |AB| + |BA| + |AB| = x+y+z+y
// S_slow = |OA| + |AB| = x+y, S_fast = 2*S_slow,所以z=x
// 即： slow从头开始走和fast从相遇位置走，距离一样，一样的节点就是入口
public ListNode detectCycle(ListNode head) {
    if(head == null) return null;
    ListNode fast = head;
    ListNode slow = head;
    boolean flag = false;
    while(fast.next !=null){
        fast = fast.next;
        if(fast.next == null){
            return null;
        }
        fast = fast.next;
        slow = slow.next;
        if(fast == slow){
            slow = head;
            flag = true;
            break;
        }
    }
    if(flag){
        while(slow != fast){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
    return null;
}

3、数组中找到重复的数字（287. Find the Duplicate Number）

题目：1--n的数放入n+1长的数组，肯定有一个重复的数字

Input: [1,3,4,2,2]
Output: 2
Input: [3,1,3,4,2]
Output: 3

// 方案一：二分法
/*
* 在区间[1, n]中搜索，首先求出中点mid，然后遍历整个数组，统计所有小于等于mid的数的个数，如果个数大于mid，则说明重复值在[mid+1, n]之间，反之，重复值应在[1, mid-1]之间，然后依次类推，直到搜索完成，此时的low就是我们要求的重复值
*/
public int findDuplicate(int[] nums) {
    int l = 0;
    int r = nums.length -1;
    while(l < r){
        int count = 0;
        int mid = l + (r-l)/2;
        for(Integer a:nums){
            if(a <= mid) count++;
        }
        if(count <= mid) l = mid + 1;
        else r = mid;
    }
    return l;
}

//方案二，类似链表有环的情况，如果有重复的元素，就一定有环。
/*
 * 从数组n+1个元素映射到从1-n的数，换检测定义，给定一个函数，和序列，定义如下：
 * x_0  = k
 * x_1 = f(x_0)
 * x_2 = f(x_1)
 * ...
 * x_(n+1) = f(x_n)
 * 假设函数f从定义域映射到它本身，此时会有3种情况。首先，如果定义域是无穷的，则序列是无限长并且没有循环的。例如，函数 f(n) = n + 1，在整数范围内满足这个性质 - 没有数字是重复的。 第二， 序列可能是一个闭合循环，这意味着存在一个i使得x_0 = x_i。在这个例子中，序列在一组值内无限循环。第三，序列有可能是的“ρ型的”，此时序列看起来像下面这样：
   x_0 -> x_1 -> ... x_k -> x_{k+1} ... -> x_{k+j}
                         ^                       |
                         |                       |
                         +-----------------------+
* 也就是说，序列从一列链条型的元素开始进入一个环，然后无限循环。我们将环的起点称为环的“入口”。
* 从x_0开始： slow = f(slow)
              fast = f(f(fast))
  当 slow==fast时。在slow=x_0，然后fast和slow每次只走一步，当再次相等时，入口元素即是重复元素
*/
public int findDuplicate(int[] nums) {
    if(nums.length == 0) return 0;
    int fast = 0;
    int slow = 0;
    int t = 0;
    while(true){
        slow = nums[slow];
        fast = nums[nums[fast]];
        if(slow == fast){
            break;
        }
    }
    while(true){
        slow = nums[slow];
        t = nums[t];
        if(slow == t){
            break;
        }
    }
    return slow;        
}

4、删除链表中重复元素，重复的元素全部删除（82. Remove Duplicates from Sorted List II）

/*
* 递归解法
*/
public ListNode deleteDuplicates(ListNode head) {
    if(head == null || head.next == null) return head;
    ListNode next = head.next;
    // 处理头结点和next节点值一样
    if(head.val == next.val){
        while(next != null && head.val == next.val){
            next = next.next;
        }
        return deleteDuplicates(next);
    }else{
        // 处理头结点和next节点值不一样
        head.next = deleteDuplicates(head.next);
        return head;
    }
} 

/**
* 非递归解法，增加一个pre节点，增加pre初始节点first，则first.next = head
*/
public ListNode deleteDuplicates(ListNode head) {
    if(head == null || head.next == null) return head;
    // 增加一个节点表示 head的pre节点
    ListNode first = new ListNode(-1);
    first.next = head;
    // 分别赋值两个节点，一个当前节点，一个pre节点
    ListNode cur = head;
    ListNode pre = first;
    //循环条件，当前节点不为null，下一个节点不会null
    while(cur !=null && cur.next != null){
        // 定义next节点，用来和cur节点比较
        ListNode next = cur.next;
        if(cur.val == next.val){
            // 继续往后试探，表示 cur 到 next的值都 相同
            while(next != null && cur.val == next.val){
                next = next.next;
            }
            // 这个点比较难思考，因为所有相同的节点都删除，所以pre指向 next，
            pre.next = next;
            cur = next;
        }else{
            // pre指向当前节点，cur向后移动
            pre = cur;
            cur = cur.next;
        }
    }
    return first.next;  // 返回初始节点的后一个
}

5、反转链表（206. Reverse Linked List）

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
// 解法：  1、 null 1->2->3->null
//         2、 null<-1 2->3->null
//         3、 null<-1<-2 3->null
// 迭代法
public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    while(head !=null){
        // 保存断开后的链接
        ListNode next = head.next;
        // 原地反转
        head.next = prev;
        prev = head;
        head = next;
    }
    return prev;
}
// 递归法
public ListNode reverseList(ListNode head) {
    if(head == null || head.next ==null) return head;
    ListNode node = reverseList(head.next);
    // 考虑第一个head，反转指针，指向null
    head.next.next = head;
    head.next = null;
    return node;
}

6、删除元素（27. Remove Element）

// Given nums = [3,2,2,3], val = 3,  return length=2. [2,2,x,x]
// Given nums = [0,1,2,2,3,0,4,2], val = 2,return length=5. [0,1,3,0,4]
// Method 1: 双指针，bengin 和 end
public int removeElement(int[] nums, int val) {
    int begin = 0;
    int end = nums.length - 1;
    while(begin <= end){
        if(nums[begin] == val){
            // 将end的值赋给begin，并且end--, 下次循环继续检查begin
            nums[begin] = nums[end--];
        }else{
            // 继续移动
            begin++;
        }
    }
    return begin;
}

// Method 2: 双指针，fast 和 slow
// fast每移动一个，如果 nums[fast]!=val,  nums[slow++] = nums[fast]
// 将不删除的元素放到他的位置上，留下的是什么元素不重要
public int removeElement(int[] nums, int val) {
    int slow = 0;
    for(int i=0;i<nums.length;i++){
        if(nums[i] != val){
            nums[slow++] = nums[i];
        }
    }
    return slow;
}

扩展，剑指offer（在 O(1) 时间内删除链表节点）

// 如果该节点不是尾节点，那么可以直接将下一个节点的值赋给该节点，然后令该节点指向下下个节点，再删除下一个节点，时间复杂度为 O(1)。
// 否则，就需要先遍历链表，找到节点的前一个节点，然后让前一个节点指向 null，时间复杂度为 O(N)。
public ListNode deleteNode(ListNode head, ListNode tobeDelete) {
    if(head == null || head.next == null || tobeDelete == null) return null;
    if(tobeDelete.next != null){
        ListNode next = tobeDelete.next;
        tobeDelete.val = next.val;
        tobeDelete.next = next.next;
    }else{
        ListNode cur = head;
        while(cur.next != null) cur = cur.next;
        cur.next = null;
    }
    return head;
}

7、删除链表中倒数第K个节点（19. Remove Nth Node From End of List）

// 思路比较简单，fast指针先走n步，然后快慢指针一起走
// 注意点，定义一个头节点指向head节点，从头结点开始循环
public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode start = new ListNode(-1);
    // 定义头节点，从头结点开始
    ListNode fast = start;
    ListNode slow = start;
    start.next = head;
    // 先走n步
    int count = 0;
    while(count < n && fast.next !=null){
        fast = fast.next;
        count++;
    }
    // 走到结尾
    while(fast.next !=null){
        fast = fast.next;
        slow = slow.next;
    }
    // 删除 slow后面的节点
    slow.next = slow.next.next;
    return start.next;
}

8、合并两个排好序的链表（21. Merge Two Sorted Lists）

// 思路比较简单，1、定义好开始节点
// 2、定义两个指针节点， l1 和 l2, 不断向后移动
// 3、走到结尾时，l1 或 l2 有剩余的节点，遍历完所有的节点
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if(l1 == null) return l2;
    if(l2 == null) return l1;
    // 步骤一
    ListNode head = null;
    if(l1.val<l2.val){
        head = l1;
        l1 = l1.next;
    }else{
        head = l2;
        l2 = l2.next;
    }
    // 步骤二
    ListNode first = head;
    while(l1 !=null && l2 !=null){
        if(l1.val < l2.val){
            head.next = l1;
            l1 = l1.next;
        }else{
            head.next = l2;
            l2 = l2.next;
        }
         head = head.next;
    }
    // 步骤三
    while(l1!=null){
        head.next = l1;
        head = head.next;
        l1 = l1.next;
    }
    while(l2!=null){
        head.next = l2;
        head = head.next;
        l2 = l2.next;
    }
    return first;
}

9、链表排序（148. Sort List）

// Method 1：归并排序，递归法，时间 O（NlgN）, 空间 O（lgN）
// 快慢指针找中点，递归两个子链表
class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode slow = head;
        ListNode fast = head.next;    // 注意点，开始fast的位置
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode mid = slow.next;    // 注意点，终止，mid的计算方式
        slow.next = null;
        return merge(sortList(head), sortList(mid));  // 递归的方式
    }
    public ListNode merge(ListNode l1, ListNode l2){
        ListNode dummy = new ListNode(-1);    // 技巧，设定dummy节点
        ListNode tail = dummy;
        while(l1 !=null && l2 !=null){
            if(l1.val > l2.val ){
                tail.next = l2;
                l2 = l2.next;
            }else{
                tail.next = l1;
                l1 = l1.next;
            }
            tail = tail.next;
        }
        if(l1 != null) tail.next = l1;
        if(l2 != null) tail.next = l2;
        return dummy.next;
    }
}
// method 2: 归并排序，自底向上

10、归并排序，自顶向下，自底向上

/*
 * 归并排序
 * 递归格式要记住 
 */
public static void mergeSort(int [] arr, int low, int high){
	if(low<high){
		int mid = (low + high)/2;
		mergeSort(arr, low, mid);
		mergeSort(arr, mid+1, high);
		merge(arr, low, mid, high);
	}
}

/*
 * 归并排序, 自底向上，迭代法
 * 两轮循环，第一轮循环 ： 一次看多少数据  1, 2, 4, 8, ....
 * 第二轮迭代: 对连续两个子区间    进行归并排序  
 */
public static void mergeSortBU(int arr[], int n){
	for(int size=1; size <= n; size += size){
		for(int i=0; i+size < n; i += size + size){
			merge(arr, i, i+size-1, Math.min(i+size+size-1, n-1));
		}
	}
}

/*
 * 合并两个有序数组
 * 需要空间存储原始 数组
 */
public static void merge(int [] arr, int low, int mid, int high){
	int [] brr = Arrays.copyOf(arr, arr.length);
	int i=low,j=mid+1,k=i;
	for(;i<=mid && j<=high;){
		if(brr[i] < brr[j]){
			arr[k++] = brr[i++];
		}else{
			arr[k++] = brr[j++];
		}
	}
	while(i<=mid){
		arr[k++] = brr[i++]; 
	}
	while(j<=high){
		arr[k++] = brr[j++];
	}
}

11、全排列（46. Permutations）

Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]
// 解法：
/*
 * 全排列   递归实现
 * 1 + 【后面的全排列】
 * 递归的实现这个过程
 * 递归出口就是 这个数组只剩下最后一个元素
 * 1，2，3，4，分别开头 ，然后交换，然后在交换回来
 * 1 【2,3,4】 交换 2【1,3,4】 3【2,1,4】 4【2,3,1】 递归实现
 */
 public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> list = new ArrayList<List<Integer>>();
    perm(nums, 0, nums.length-1, list);
    return list;
}
public static void perm(int[] nums, int l, int r, List<List<Integer>> list){
    if(l == r){
        List<Integer> li = genList(nums);   // 每次出口就是一个排列
        list.add(li);
    }else{
        for(int i=l;i<=r;i++){
            swap(nums, l, i);    // 交换
            perm(nums, l+1, r, list); 
            swap(nums, l, i);   // 交换回来
        }  
    } 
}
public static void swap(int[] nums, int i, int j){
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}
public static List<Integer> genList(int[] nums){
    List<Integer> li = new ArrayList<Integer>();
    for(int i=0;i<nums.length;i++){
        li.add(nums[i]);
    }
    return li;
}