力扣学习录04--代码随想录：数组、链表

Huang Zhiwei
  2023-08-30 22:16:54 2023-08-30 22:16 创建   2023-09-02 23:41:50 2023-09-02 23:41 更新    

二刷代码随想录，感觉轻松很多，本节记录数组、链表两部分的内容，其余内容陆续更新中。

前两节比较简单，提供了Java/go语言的版本，后面困难起来了可能就不大会用Go了。

代码随想录视频链接：代码随想录的个人空间_哔哩哔哩_bilibili

代码随想录网站链接：代码随想录 (programmercarl.com)

数组

01 二分法 | 二分查找法 | 二分搜索法 leetcode704

1
2
*给定一个n个元素有序的（升序）整型数组nums和一个目标值target，
*写一个函数搜索nums中的target，如果目标值存在返回下标，否则返回-1。

思路：要分清楚左右区间的开闭情况，其他都是很容易的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
* 二分法的思想就是要分清楚左右区间的开闭情况，其他都是很容易的
* 以下代码中A方法以左闭右闭来写的，B方法以做闭右开方法来写的
public class Array01HalfSearch {
    public static void main(String[] args) {
        // 测试用例
        int[] arrays = new int[]{-1,0,3,5,9,12};
        System.out.println(halfSearchB(arrays, 9));
    }

    public static int halfSearchA(int[] arrays,int target){
        int left = 0,right= arrays.length -1 ;
        int middle;
        // 左闭右闭中需要考虑左右区间相等的情况，它仍然包含了一个数，所以循环应当继续
        while (left <= right){
            middle = left + (right-left)/2;
            if(arrays[middle] > target){
                right = middle -1;
            }else if(arrays[middle] <target){
                left = middle +1;
            }else {
                return middle;
            }
        }
        return -1;
    }
    public static int halfSearchB(int[] arrays,int target){
        // 左闭右开中，右边界就是length
        int left = 0,right= arrays.length ;
        int middle;
        // 左闭右开中，左右区间相等的情况不包含数，循环应当终止，所以判据应当是小于
        while (left < right){
            middle = left + (right-left)/2;
            if(arrays[middle] > target){
                // 和左闭右闭的区别在这里，如果中间的数字比target大，那么右区间的应当截止到middle
                right = middle;
            }else if(arrays[middle] <target){
                left = middle + 1;
            }else {
                return middle;
            }
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
package main

import "fmt"

func main() {
	arrays := []int{-1, 0, 3, 5, 9, 12}
	target := 9
	fmt.Println(search(arrays, target))
	return
}

func search(nums []int, target int) int {
	high := len(nums) - 1
	low := 0
	for low <= high {
		mid := low + (high-low)/2
		if nums[mid] == target {
			return mid
		} else if nums[mid] > target {
			high = mid - 1
		} else {
			low = mid + 1
		}
	}
	return -1
}

02 移除元素 leetcode27

1
2
3
4
5
6
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并**原地**修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。
示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

思路1：暴力的解法就是两层for循环，一个for循环遍历数组元素 ，第二个for循环更新数组。

思路2：双指针写法，慢指针找到要删除的数字V的位置，然后等待；快指针向后走，将找到的第一个不是V的数字，然后赋给慢指针指向的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Array02DeleteElement {
    public static void main(String[] args) {
        int[] arrays = new int[]{0,1,2,2,3,0,4,2};
        System.out.println(removeElement(arrays,2));
    }
    public static int removeElement(int[] nums, int val) {
        int fast = 0,slow = 0;
        while (fast<nums.length){
            if(nums[fast] == val){
                fast ++;
            }else {
                nums[slow] = nums[fast];
                fast ++;
                slow ++;
            }
        }
        return slow;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
package main

import "fmt"

func main() {
	arrays := []int{0, 1, 2, 2, 3, 0, 4, 2}
	target := 2
	fmt.Println(removeElement(arrays, target))
}

func removeElement(nums []int, val int) int {
	fast := 0
	slow := 0
	for fast < len(nums) {
		if nums[fast] == val {
			fast++
		} else {
			nums[slow] = nums[fast]
			slow++
			fast++
		}
	}
	return slow
}

03 有序数组的平方 leetcode977

1
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

思路1：直接平方然后排序 如java的A方法

思路2：用两个指针直线该数组的首尾，然后移动指针，向结果集中挨个添加更大的那个数值即可，如java的B方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Array03ArraySquare {
    public static void main(String[] args) {
        int[] arrays = new int[]{-7,-3,2,3,11};
        System.out.println(Arrays.toString(sortedSquaresA(arrays)));
        System.out.println(Arrays.toString(sortedSquaresB(arrays)));
    }
    public static int[] sortedSquaresA(int[] nums){
        int[] result = new int[nums.length];
        for(int i = 0;i<nums.length;i++){
            result[i] = nums[i]*nums[i];
        }
        Arrays.sort(result);
        return result;
    }
    public static int[] sortedSquaresB(int[] nums){
        int left = 0,right = nums.length-1;
        int[] result = new int[nums.length];
        for(int i = nums.length-1;i>=0;i--){
            if(nums[left]*nums[left] > nums[right]*nums[right]){
                result[i] = nums[left]*nums[left];
                left ++;
            }else {
                result[i] = nums[right]*nums[right];
                right --;
            }
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
package main

import "fmt"

func main() {
	arrays := []int{-7, -3, 2, 3, 11}
	fmt.Println(sortedSquares(arrays))
}
func sortedSquares(nums []int) []int {
	left := 0
	right := len(nums) - 1
	k := len(nums) - 1
	result := make([]int, len(nums))
	for k >= 0 {
		lm, rm := nums[left]*nums[left], nums[right]*nums[right]
		if lm > rm {
			result[k] = lm
			left++
		} else {
			result[k] = rm
			right--
		}
		k--
	}
	return result
}

04 长度最小的子数组 leetcode209

1
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

思路1：双重循环法，用两个for循环，然后不断的寻找符合条件的子序列，时间复杂度很明显是O(n^2)。

思路2：双指针模拟滑动窗口法，用i标识起始位置，j标识终止位置，先让j出发收集一路上的数值和，直到数值和大于sum；然后让i往后移动，挨个减去i对应位置的数值，直到数值和比sum小；接下来再移动j，以此类推。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Array04MinSubArrayLen {
    public static void main(String[] args) {
        int[] arrays = new int[]{1,4,4};
        System.out.println(minSubArrayLen(4,arrays));
    }
    public static int minSubArrayLen(int target,int[] nums){
        int i = 0,j=0,sum = 0,result = Integer.MAX_VALUE;
        while(j < nums.length){
            sum += nums[j];
            while (sum >= target){
                result = Math.min(result,j-i+1);
                sum -= nums[i];
                i++;
            }
            j++;
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func minSubArrayLen(target int, nums []int) int {
	left, right, sum, result := 0, 0, 0, len(nums)+1
	for right < len(nums) {
		sum += nums[right]
		for sum >= target {
			result = int(math.Min(float64(result), float64(right-left+1)))
			sum -= nums[left]
			left++
		}
		right++
	}
	if result == len(nums)+1 {
		return 0
	} else {
		return result
	}
}

05 螺旋矩阵Ⅱ leetcode59

1
给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

思路1：模拟法，本题目就是纯正的模拟题，坚持左闭右开的区间定义，这样每次转圈的时候要处理的边的长度就是一样的。转圈的数量应当等于n/2，如果是奇数也没关系就最后处理中间的最后一个值。如generateMatrixA 方法所示。

思路2：模拟法（较为混乱的版本），使用究极原始的模拟法，记录每一个转向标志，剩余边的长度，如generateMatrixB 方法所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
public class Array05GenerateMatrix {
    public static void main(String[] args) {
        int[][] result = generateMatrixA(5);
        for(int i = 0;i<5;i++){
            System.out.println(Arrays.toString(result[i]));
        }
    }

    public static int[][] generateMatrixA(int n) {
        //坚持左开右闭原则
        int i = 0;
        int[][] result = new int[n][n];
        int start = 1;
        while(i < n/2){
            //从左到右的横向
            for(int size = 0;size < n - 1 - 2*i;size++){
                result[i][size+i] = start++;
            }
            //从上到下的纵向
            for(int size = 0;size < n - 1 - 2*i;size++){
                result[size+i][n-1-i] = start++;
            }
            //从右到左的横向
            for(int size = 0;size < n - 1 - 2*i;size++){
                result[n-1-i][n-1-i-size] = start++;
            }
            //从下到上的纵向
            for(int size = 0;size < n - 1 - 2*i;size++){
                result[n-1-i-size][i] = start++;
            }
            i ++;
        }
        if(n % 2 == 1){
            result[n/2][n/2] = start++;
        }
        return result;
    }
    public static int[][] generateMatrixB(int n) {
        int[][] ans = new int[n][n];
        int i = 0;
        int j = 0;
        int index = 1;
        boolean upflag = false;
        boolean downflag = false;
        boolean leftflag = false;
        boolean rightflag = true;
        // 左右边界和上下边界 0,2 0,2
        int rightend = n-1;
        int leftstart = 0;
        int downend = n-1;
        int upstart = 0;

        // 转向时需要修改边界
        // 判断到头了就转向
        while(index <= n*n){
            ans[i][j] = index;
            index += 1;
            //四个方向
            if(rightflag && j<rightend){j += 1;}
            else if(leftflag && j>leftstart){j -= 1;}
            else if(downflag && i<downend){i += 1;}
            else if(upflag && i > upstart){i -= 1;}
            //转向
            else if( rightflag && j == rightend){
                rightflag = false;
                downflag = true;
                i += 1;
                upstart += 1;}
            else if( leftflag && j==leftstart){
                leftflag = false;
                upflag = true;
                i -= 1;
                downend -= 1;}
            else if(downflag && i==downend) {
                downflag = false;
                leftflag = true;
                j -= 1;
                rightend -= 1;}
            else if(upflag && i == upstart){
                upflag = false;
                rightflag = true;
                j += 1;
                leftstart += 1;}
        }
        return ans;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
package main

import "fmt"

func main() {
	target, p := 5, 0
	result := generateMatrixA(target)
	for target > 0 {
		fmt.Println(result[p])
		target--
		p++
	}
}
func generateMatrixA(n int) [][]int {
	// 坚持左开右闭原则
	i, start, size := 0, 1, 0
	result := make([][]int, n)
	for t := 0; t < n; t++ {
		result[t] = make([]int, n)
	}
	for i < n/2 {
		//从左到右的横向
		for size < n-1-2*i {
			result[i][size+i] = start
			size++
			start++
		}
		size = 0
		//从上到下的纵向
		for size < n-1-2*i {
			result[size+i][n-1-i] = start
			size++
			start++
		}
		size = 0
		//从右到左的横向
		for size < n-1-2*i {
			result[n-1-i][n-1-i-size] = start
			size++
			start++
		}
		size = 0
		//从下到上的纵向
		for size < n-1-2*i {
			result[n-1-i-size][i] = start
			size++
			start++
		}
		size = 0
		i++
	}
	if n%2 == 1 {
		result[n/2][n/2] = start
	}
	return result
}

链表

写在前面

本节记录一种由字符串构建链表的方法，记录基本链表节点的类。

以下两个代码块是Java语言的

1
2
3
4
5
6
7
8
9
10
11
12
13
public ListNode generateListNodeFromArray(int[] array){
        if(array == null || array.length ==0){
            return null;
        }
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        for(int i = 0;i< array.length;i++){
            ListNode newNode = new ListNode(array[i]);
            current.next = newNode;
            current = newNode;
        }
        return dummy.next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
/**
 * @description: 链表节点类
 * @author: Huang Zhiwei
 * @time: 2023/8/31 22:26
 */
public class ListNode {
    int val;
    ListNode next;
    ListNode() {};
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

以下两个代码块是Go语言的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func createLinkedList(nums []int) *ListNode {
	if len(nums) == 0 {
		return nil
	}

	head := &ListNode{Val: nums[0]}
	curr := head

	for i := 1; i < len(nums); i++ {
		node := &ListNode{Val: nums[i]}
		curr.Next = node
		curr = node
	}

	return head
}
1
2
3
4
5
6
package ListNode

type ListNode struct {
	Val  int
	Next *ListNode
}

01移除链表元素 leetcode203

1
删除链表中等于给定值 val 的所有节点。

思路1：用虚拟头节点法，创建一个虚拟的头节点dummy，让dummy的next指向实际链表的头节点。然后挨个遍历删除即可，如方法A。

思路2：不添加虚拟头节点，使用判断先将头部的等于val的删除，如方法B。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public class ListNode01RemoveElements {
    public static void main(String[] args) {
        ListNode listNode = ListNode00GenerateListNode.generateListNodeFromArray(new int[]{1,2,6,3,4,5,6});
        listNode = removeElementsB(listNode,6);
        while(listNode != null){
            System.out.print(listNode.val+" ");
            listNode = listNode.next;
        }
    }
    public static ListNode removeElementsA(ListNode head, int val) {
        if(head == null){return head;}

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode cur = head;
        while (cur != null){
            if(cur.val == val){
                pre.next = cur.next;
            }else {
                pre = cur;
            }
            cur = cur.next;
        }
        return dummy.next;
    }
    public static ListNode removeElementsB(ListNode head, int val){
        while (head != null && head.val == val){
            head = head.next;
        }
        if(head == null){
            return head;
        }
        //现在的头节点必然不等于val
        ListNode pre = head;
        ListNode cur = head.next;
        while (cur != null){
            if(cur.val == val){
                pre.next = cur.next;
            }else {
                pre = cur;
            }
            cur = cur.next;
        }
        return head;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
package main

func main() {
	listnode := createLinkedList([]int{1, 2, 3, 4, 5, 6})
	listnode = removeElements(listnode, 6)
	printLinkedList(listnode)
}

func removeElements(head *ListNode, val int) *ListNode {
	dummyHead := &ListNode{}
	dummyHead.Next = head
	cur := dummyHead
	for cur != nil && cur.Next != nil {
		if cur.Next.Val == val {
			cur.Next = cur.Next.Next
		} else {
			cur = cur.Next
		}
	}
	return dummyHead.Next
}

go语言使用了多个文件，执行需要go run .\ListNode.go .\ListNode00GenerateListNode.go .\ListNode01RemoveElements.go

02 设计链表 leetcode707

1
2
3
4
5
6
7
在链表类中实现这些功能：

get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

设计链表是重要的练习，首先需要一个虚拟头节点、一个链表的size，一个初始化函数。其余的就是实现这些功能了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
public class ListNode02MyLinkedList {
    ListNode head;
    int size;
    ListNode02MyLinkedList(){
        head = new ListNode(0);
        size = 0;
    }
    //获取第index个节点的数值，注意index是从0开始的，第0个节点就是头结点
    public int get(int index) {
        if(index < 0 || index > size-1){
            return -1;
        }
        ListNode cur = head;
        while (index >= 0 ){
            cur = cur.next;
            index --;
        }
        return cur.val;
    }
    //在链表最前面插入一个节点，等价于在第0个元素前添加
    public void addAtHead(int val) {
        addAtIndex(0,val);
    }
    //在链表的最后插入一个节点，等价于在(末尾+1)个元素前添加
    public void addAtTail(int val) {
        addAtIndex(size,val);
    }
    // 在第 index 个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
    // 如果 index 等于链表的长度，则说明是新插入的节点为链表的尾结点
    // 如果 index 大于链表的长度，则返回空
    public void addAtIndex(int index, int val) {
        if(index > size){
            return;
        }
        if(index <0){index = 0;}
        size++;
        ListNode pre = head;
        for(int i = 0;i< index;i++){
            pre = pre.next;
        }
        ListNode toAdd = new ListNode(val);
        // 打断，把前后分别拼接起来
        toAdd.next = pre.next;
        pre.next = toAdd;
    }
    //删除第index个节点
    public void deleteAtIndex(int index) {
        if(index >= size || index < 0){
            return;
        }
        size--;
        if(index == 0){
            head = head.next;
            return;
        }
        ListNode pre = head;
        for(int i = 0;i< index;i++){
            pre = pre.next;
        }
        // 打断，把前后分别拼接起来
        pre.next = pre.next.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
package main

type MyLinkedList struct {
	dummyHead *ListNode
	Size      int
}

func main() {
	list := Constructor()     // 初始化链表
	list.AddAtHead(100)       // 在头部添加元素
	list.AddAtTail(242)       // 在尾部添加元素
	list.AddAtTail(777)       // 在尾部添加元素
	list.AddAtIndex(1, 99999) // 在指定位置添加元素 // 打印链表
}

func Constructor() MyLinkedList {
	newNode := &ListNode{
		0,
		nil,
	}
	return MyLinkedList{
		dummyHead: newNode,
		Size:      0,
	}
}
func (this *MyLinkedList) Get(index int) int {
	if this == nil || index < 0 || index > this.Size {
		return -1
	}
	cur := this.dummyHead.Next
	for i := 0; i < index; i++ {
		cur = cur.Next
	}
	return cur.Val
}
func (this *MyLinkedList) AddAtHead(val int) {
	newNode := &ListNode{Val: val}     // 创建新节点
	newNode.Next = this.dummyHead.Next // 新节点指向当前头节点
	this.dummyHead.Next = newNode      // 新节点变为头节点
	this.Size++                        // 链表大小增加1
}
func (this *MyLinkedList) AddAtTail(val int) {
	newNode := &ListNode{Val: val} // 创建新节点
	cur := this.dummyHead          // 设置当前节点为虚拟头节点
	for cur.Next != nil {          // 遍历到最后一个节点
		cur = cur.Next
	}
	cur.Next = newNode // 在尾部添加新节点
	this.Size++        // 链表大小增加1
}
func (this *MyLinkedList) AddAtIndex(index int, val int) {
	if index < 0 { // 如果索引小于0，设置为0
		index = 0
	} else if index > this.Size { // 如果索引大于链表长度，直接返回
		return
	}

	newNode := &ListNode{Val: val} // 创建新节点
	cur := this.dummyHead          // 设置当前节点为虚拟头节点
	for i := 0; i < index; i++ {   // 遍历到指定索引的前一个节点
		cur = cur.Next
	}
	newNode.Next = cur.Next // 新节点指向原索引节点
	cur.Next = newNode      // 原索引的前一个节点指向新节点
	this.Size++             // 链表大小增加1
}
func (this *MyLinkedList) DeleteAtIndex(index int) {
	if index < 0 || index >= this.Size { // 如果索引无效则直接返回
		return
	}
	cur := this.dummyHead        // 设置当前节点为虚拟头节点
	for i := 0; i < index; i++ { // 遍历到要删除节点的前一个节点
		cur = cur.Next
	}
	if cur.Next != nil {
		cur.Next = cur.Next.Next // 当前节点直接指向下下个节点，即删除了下一个节点
	}
	this.Size-- // 注意删除节点后应将链表大小减一
}

03 反转链表 leetcode206

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

思路1：使用双指针写法，创建一个pre，cur，temp，分别标识前一个，当前，下一个。那么步骤应当为：

temp后移一位；

cur指向pre；

pre移动到cur；

cur移动到temp；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class ListNode03ReverseList {
    public static void main(String[] args) {
        ListNode listNode = ListNode00GenerateListNode.generateListNodeFromArray(new int[]{1,2,3,4,5,6});
        listNode = reverseList(listNode);
    }
    public static ListNode reverseList(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        ListNode temp = head;
        while (temp != null){
            temp = temp.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
package main

func main() {
	listnode := createLinkedList([]int{1, 2, 3, 4, 5, 6})
	listnode = reverseList(listnode)
	printLinkedList(listnode)
}
func reverseList(head *ListNode) *ListNode {
	var pre *ListNode
	cur := head
	temp := head
	for temp != nil {
		temp = temp.Next
		cur.Next = pre
		pre = cur
		cur = temp
	}
	return pre
}

04 两两交换链表中的节点 leetcode24

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

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

思路1：虚拟头节点法，创建一个虚拟头节点dummy，令cur = dummy;

循环终止条件：cur.next ==null || cur.next.next == null

循环体内部操作：以1，2，3，4，5，6为例

temp(1) =cur.next

temp1 (3) = cur.next.next.next

[cur.next](http://cur.next) = cur.next.next

[cur.next.next](http://cur.next.next) = temp

[temp.next](http://temp.next) = temp1

cur = cur.next.next

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class ListNode04SwapPairs {
    public static void main(String[] args) {
        ListNode listNode = ListNode00GenerateListNode.generateListNodeFromArray(new int[]{1,2,3,4,5,6});
        ListNode00GenerateListNode.printListNode(swapPairs(listNode));
    }
    public static ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = dummy;
        ListNode temp,temp1;
        while (cur.next != null && cur.next.next != null){
            temp = cur.next;
            temp1 = cur.next.next.next;

            cur.next = cur.next.next;
            cur.next.next = temp;
            temp.next = temp1;
            cur = cur.next.next;
        }
        return dummy.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
package main

func main() {
	listnode := createLinkedList([]int{1, 2, 3, 4, 5, 6})
	printLinkedList(swapPairs(listnode))
}

func swapPairs(head *ListNode) *ListNode {
	dummy := &ListNode{
		Next: head,
	}

	cur := dummy
	temp, temp1 := dummy, dummy
	for cur.Next != nil && cur.Next.Next != nil {
		temp = cur.Next
		temp1 = cur.Next.Next.Next

		cur.Next = cur.Next.Next
		cur.Next.Next = temp
		temp.Next = temp1
		cur = cur.Next.Next
	}
	return dummy.Next
}

05 删除链表的倒数第N个节点 leetcode19

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

典型的快慢指针法，让快节点先走n步，然后慢节点再开始，最后删除慢节点即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class ListNode05RemoveNthFromEnd {
    public static void main(String[] args) {
        ListNode listNode = ListNode00GenerateListNode.generateListNodeFromArray(new int[]{1,2,3,4,5});
        ListNode00GenerateListNode.printListNode(removeNthFromEnd(listNode,2));
    }
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode fast = dummy;
        ListNode slow = dummy;
        for(int i = 0;i<n;i++){
            fast = fast.next;
        }
        while (fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package main

func main() {
	listnode := createLinkedList([]int{1, 2, 3, 4, 5})
	printLinkedList(removeNthFromEnd(listnode, 2))
}
func removeNthFromEnd(head *ListNode, n int) *ListNode {
	dummy := &ListNode{
		Next: head,
	}
	fast := dummy
	slow := dummy
	for i := 0; i < n; i++ {
		fast = fast.Next
	}
	for fast.Next != nil {
		fast = fast.Next
		slow = slow.Next
	}
	slow.Next = slow.Next.Next
	return dummy.Next
}

06 链表相交 leetcode 面试题02.07

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

这道题有很多种解法，比较常规的是哈希集合法和链表长度检查法，leetcode官方提供的基于追击的双指针太抽象了，不可能想出来的。

思路1：哈希集合法，遍历一遍链表A，将节点添加到一个哈希集合中去，在遍历链表B，将节点添加到哈希集合中去，如果有冲突那么就输出这个节点；如果全部添加进去也没反应就返回null，如方法A

思路2：求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置，比较两个对象是否相等即可，如方法B

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
public class ListNode06GetIntersectionNode {
    public static void main(String[] args) {
        ListNode listNodeA = ListNode00GenerateListNode.generateListNodeFromArray(new int[]{1,2,3,4,5});
        ListNode listNodeB = ListNode00GenerateListNode.generateListNodeFromArray(new int[]{9,8,7});
        listNodeB.next = listNodeA.next;
        ListNode00GenerateListNode.printListNode(getIntersectionNode(listNodeA,listNodeB));
    }
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        HashSet<ListNode> set = new HashSet<>();
        while (headA != null){
            set.add(headA);
            headA = headA.next;
        }
        while (headB != null){
            if(set.contains(headB)){
                return headB;
            }
            headB = headB.next;
        }
        return null;
    }
		public static ListNode getIntersectionNodeB (ListNode headA, ListNode headB){
        ListNode curA = headA;
        ListNode curB = headB;
        int lenA = 0,lenB = 0;
        while (curA != null){
            lenA ++;
            curA = curA.next;
        }
        while (curB != null){
            lenB ++;
            curB = curB.next;
        }
        curA = headA;
        curB = headB;
        if(lenB > lenA){
            int tmpLen = lenA;
            lenA =lenB;
            lenB=tmpLen;
            
            ListNode tmpNode = curA;
            curA = curB;
            curB = tmpNode;
        }
        //长度差
        int gap = lenA -lenB;
        while (gap-- >0){
            curA = curA.next;
        }
        // 遍历curA和curB，遇到相同的则直接返回
        while (curA != null){
            if (curA ==curB){
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func main() {
	listnodeA := createLinkedList([]int{1, 2, 3, 4, 5})
	listnodeB := createLinkedList([]int{9, 8, 7})
	listnodeB.Next = listnodeA.Next
	printLinkedList(getIntersectionNode(listnodeA, listnodeB))
}

func getIntersectionNode(headA, headB *ListNode) *ListNode {
	set := make(map[*ListNode]bool)

	// 遍历链表A，将节点存入集合
	for headA != nil {
		set[headA] = true
		headA = headA.Next
	}
	// 遍历链表B，检查节点是否存在于集合中
	for headB != nil {
		if set[headB] {
			return headB
		}
		headB = headB.Next
	}
	return nil
}

07 环形链表 leetcode142

1
2
3
题意： 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。

经典快慢指针法如方法A，也可以使用哈希集合法如方法B，这道题是比较简单的。需要注意的是返回的listnode是环的入口，不是相遇的任意节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class ListNode07DetectCycle {
    public static void main(String[] args) {
        ListNode listNode = ListNode00GenerateListNode.generateListNodeFromArray(new int[]{1,2,3,4,5});
        listNode.next.next.next.next = listNode.next.next;
        ListNode00GenerateListNode.printListNode(detectCycleA(listNode));
    }
    public static ListNode detectCycleA(ListNode head) {

        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                ListNode index1 = fast;
                ListNode index2 = head;
                // 两个指针，从头结点和相遇结点，各走一步，直到相遇，相遇点即为环入口
                while (index1 != index2) {
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        return null;
    }
    public static ListNode detectCycleB(ListNode head) {
        HashSet<ListNode> set = new HashSet<>();
        while (head != null){
            if(set.contains(head)){
                return head;
            }else {
                set.add(head);
            }
            head = head.next;
        }
        return null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
package main

func main() {
	listnode := createLinkedList([]int{1, 2, 3, 4, 5})
	listnode.Next.Next.Next.Next = listnode.Next
	printLinkedList(detectCycle(listnode))
}
func detectCycle(head *ListNode) *ListNode {
	set := make(map[*ListNode]bool)
	for head != nil {
		if set[head] {
			return head
		} else {
			set[head] = true
		}
		head = head.Next
	}
	return nil
}
  • 标题: 力扣学习录04--代码随想录：数组、链表
  • 作者: Huang Zhiwei
  • 创建于: 2023-08-30 22:16:54
  • 更新于: 2023-09-02 23:41:50
  • 链接: https://huangzhw0221.github.io/2023/08/30/Leetcode04/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
 评论
此页目录
力扣学习录04--代码随想录：数组、链表
  1. 数组
    1. 01 二分法 | 二分查找法 | 二分搜索法 leetcode704
    2. 02 移除元素 leetcode27
    3. 03 有序数组的平方 leetcode977
    4. 04 长度最小的子数组 leetcode209
    5. 05 螺旋矩阵Ⅱ leetcode59
  2. 链表
    1. 写在前面
    2. 01移除链表元素 leetcode203
    3. 02 设计链表 leetcode707
    4. 03 反转链表 leetcode206
    5. 04 两两交换链表中的节点 leetcode24
    6. 05 删除链表的倒数第N个节点 leetcode19
    7. 06 链表相交 leetcode 面试题02.07
    8. 07 环形链表 leetcode142