刷题

4、linkedList

算法
阅读次数: 0
本文字数: 1.4k 阅读时长: 8 分钟

链表结构体定义

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
public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (o == null || getClass() != o.getClass()) {
            return false;
        }
        ListNode listNode = (ListNode) o;
        boolean valueEqual = val == listNode.val;
        boolean nextEqual = (next == null && listNode.next == null) || (next != null && next.equals(listNode.next));
        return valueEqual && nextEqual;
    }

    @Override
    public int hashCode() {
        return Objects.hash(val, next);
    }
}

链表相关操作

创建链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 创建链表
 */
public static ListNode createList(int[] arrays) {
    if (arrays == null || arrays.length <= 0) {
        return null;
    }
    ListNode head = null;
    ListNode cur = null;
    for (int val : arrays) {
        ListNode newNode = new ListNode(val);
        if (head == null) {
            head = newNode;
            cur = head;
        } else {
            cur.next = newNode;
            cur = cur.next;
        }
    }
    return head;
}

找到链表的最后一个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * 找到最后一个节点
 */
public static ListNode findLastNode(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode lastNode = head;
    while (lastNode.next != null) {
        lastNode = lastNode.next;
    }
    return lastNode;
}

删除一个节点

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
/**
 * 删除一个节点
 */
public static ListNode deleteNode(ListNode head, ListNode toDelete) {
    if (toDelete == null || head == null) {
        return null;
    }
    ListNode tmp;
    if (head.val == toDelete.val) {
        tmp = head;
        head = head.next;
        tmp.next = null;
        return head;
    }
    ListNode cur = head;
    while (cur != null && cur.next != null) {
        if (cur.next.val == toDelete.val) {
            tmp = cur.next;
            cur.next = cur.next.next;
            tmp.next = null;
        }
        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
22
23
24
25
26
27
/**
 * 插入一个节点或者链表
 */
public static ListNode insertNode(ListNode head, ListNode toInsert, int pos) {
    if (pos < 0 || head == null || toInsert == null) {
        return head;
    }
    int count = 0;
    ListNode curNode = head;
    if (pos > 0) {
        while (curNode.next != null) {
            curNode = curNode.next;
            count++;
            if (count == pos) {
                break;
            }
        }
    }
    if (count == pos) {
        ListNode tmp = curNode.next;
        curNode.next = toInsert;
        //找到insertNode的最后一个节点指向tmp
        ListNode lastNodeOfInsertNode = findLastNode(toInsert);
        lastNodeOfInsertNode.next = tmp;
    }
    return head;
}

反转链表

使用stack实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 反转链表，使用stack实现
 */
public static ListNode reverseListWithStack(ListNode head) {
    if (head == null) {
        return null;
    }
    Stack<ListNode> stack = new Stack<>();
    stack.push(head);
    while (head.next != null) {
        stack.push(head.next);
        head.next = head.next.next;
    }
    ListNode newHead = stack.pop();
    ListNode pNode = newHead;
    while (!stack.isEmpty()) {
        ListNode curNode = stack.pop();
        pNode.next = curNode;
        pNode = curNode;
    }
    pNode.next = null;
    return newHead;
}

使用双向指针实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * 反转链表，使用双指针实现
 */
public static ListNode reverseListWithDoublePointer(ListNode head) {
    ListNode tmp;
    ListNode pre = null;
    while (head != null) {
        tmp = head.next;
        head.next = pre;
        pre = head;
        head = tmp;
    }
    return pre;
}

单元测试

删除节点

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
package com.easyliu.test.linklist;

import org.junit.Assert;
import org.junit.Test;

public class DeleteNodeTest {

    /**
     * 自测用例：
     * 1、head为null
     * 2、要删除的节点为null
     * 3、删除头部的节点
     * 4、删除尾部的节点
     * 5、删除中间节点
     * 6、有多个val一样的节点，删除第一个相等的节点
     */
    @Test
    public void testNullHead() {
        //arrange
        //act
        ListNode result = ListOperate.deleteNode(null, null);
        //verify
        Assert.assertNull(result);
    }

    @Test
    public void testNulToDeleteNode() {
        //arrange
        ListNode listNode = ListOperate.createList(new int[]{1, 2});
        //act
        ListNode result = ListOperate.deleteNode(listNode, null);
        //verify
        Assert.assertNull(result);
    }

    @Test
    public void testDeleteHeadNode() {
        //arrange
        ListNode head = ListOperate.createList(new int[]{1, 2});
        ListNode toDeleteNode = ListOperate.createList(new int[]{1});
        ListNode expectList = ListOperate.createList(new int[]{2});
        //act
        ListNode result = ListOperate.deleteNode(head, toDeleteNode);
        //verify
        Assert.assertEquals(expectList, result);
    }

    @Test
    public void testDeleteTailNode() {
        //arrange
        ListNode head = ListOperate.createList(new int[]{1, 2});
        ListNode toDeleteNode = ListOperate.createList(new int[]{2});
        ListNode expectList = ListOperate.createList(new int[]{1});
        //act
        ListNode result = ListOperate.deleteNode(head, toDeleteNode);
        //verify
        Assert.assertEquals(expectList, result);
    }

    @Test
    public void testDeleteMiddleNode() {
        //arrange
        ListNode head = ListOperate.createList(new int[]{1, 2, 3});
        ListNode toDeleteNode = ListOperate.createList(new int[]{2});
        ListNode expectList = ListOperate.createList(new int[]{1, 3});
        //act
        ListNode result = ListOperate.deleteNode(head, toDeleteNode);
        //verify
        Assert.assertEquals(expectList, result);
    }

    @Test
    public void testDeleteRepeatNode() {
        //arrange
        ListNode head = ListOperate.createList(new int[]{1, 2, 2, 3});
        ListNode toDeleteNode = ListOperate.createList(new int[]{2});
        ListNode expectList = ListOperate.createList(new int[]{1, 2, 3});
        //act
        ListNode result = ListOperate.deleteNode(head, toDeleteNode);
        //verify
        Assert.assertEquals(expectList, 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
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
89
90
91
92
93
94
package com.easyliu.test.linklist;

import org.junit.Assert;
import org.junit.Test;

public class InsertNodeTest {

    /**
     * 自测用例
     * 1、pos小于0
     * 2、head为null
     * 3、toInsertNode为null
     * 4、pos=0
     * 5、pos为size-1
     * 6、pos>0&&pos<size-1
     * 7、toInsert有多个节点
     */
    @Test
    public void testNullHead() {
        //arrange
        //act
        ListNode result = ListOperate.insertNode(null, null, 0);
        //verify
        Assert.assertNull(result);
    }

    @Test
    public void testNegativePos() {
        //arrange
        ListNode listNode = ListOperate.createList(new int[]{1, 2, 3});
        //act
        ListNode result = ListOperate.insertNode(listNode, null, -1);
        //verify
        Assert.assertEquals(listNode, result);
    }

    @Test
    public void testNullInsertNode() {
        //arrange
        ListNode listNode = ListOperate.createList(new int[]{1, 2, 3});
        //act
        ListNode result = ListOperate.insertNode(listNode, null, 0);
        //verify
        Assert.assertEquals(listNode, result);
    }

    @Test
    public void testZeroPos() {
        //arrange
        ListNode listNode = ListOperate.createList(new int[]{1, 2, 3});
        ListNode insertNode = ListOperate.createList(new int[]{1});
        ListNode expectList = ListOperate.createList(new int[]{1, 1, 2, 3});
        //act
        ListNode result = ListOperate.insertNode(listNode, insertNode, 0);
        //verify
        Assert.assertEquals(expectList, result);
    }

    @Test
    public void testMaxPos() {
        //arrange
        ListNode listNode = ListOperate.createList(new int[]{1, 2, 3});
        ListNode insertNode = ListOperate.createList(new int[]{1});
        ListNode expectList = ListOperate.createList(new int[]{1, 2, 3, 1});
        //act
        ListNode result = ListOperate.insertNode(listNode, insertNode, 2);
        //verify
        Assert.assertEquals(expectList, result);
    }

    @Test
    public void testMiddlePos() {
        //arrange
        ListNode listNode = ListOperate.createList(new int[]{1, 2, 3});
        ListNode insertNode = ListOperate.createList(new int[]{1});
        ListNode expectList = ListOperate.createList(new int[]{1, 2, 1, 3});
        //act
        ListNode result = ListOperate.insertNode(listNode, insertNode, 1);
        //verify
        Assert.assertEquals(expectList, result);
    }

    @Test
    public void testMultiNodeOfInsert() {
        //arrange
        ListNode listNode = ListOperate.createList(new int[]{1, 2, 3});
        ListNode insertNode = ListOperate.createList(new int[]{5, 6, 7, 8});
        ListNode expectList = ListOperate.createList(new int[]{1, 2, 5, 6, 7, 8, 3});
        //act
        ListNode result = ListOperate.insertNode(listNode, insertNode, 1);
        //verify
        Assert.assertEquals(expectList, 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
package com.easyliu.test.linklist;

import org.junit.Assert;
import org.junit.Test;

public class ReverseListTest {

    @Test
    public void testNullInput() {
        //arrange
        ListNode head = null;
        //act
        ListNode result = ListOperate.reverseListWithStack(head);
        ListNode doubleResult = ListOperate.reverseListWithDoublePointer(head);
        //verify
        Assert.assertNull(result);
        Assert.assertNull(doubleResult);
    }

    @Test
    public void testSingleNodeNormal() {
        //arrange
        ListNode listOne = ListOperate.createList(new int[]{1});
        ListNode listTwo = ListOperate.createList(new int[]{1});
        //act
        ListNode result = ListOperate.reverseListWithStack(listOne);
        ListNode doubleResult = ListOperate.reverseListWithDoublePointer(listTwo);
        //verify
        ListNode expect = ListOperate.createList(new int[]{1});
        Assert.assertEquals(expect, result);
        Assert.assertEquals(expect, doubleResult);
    }

    @Test
    public void testNormal() {
        //arrange
        ListNode listOne = ListOperate.createList(new int[]{1, 2, 3, 4, 5});
        ListNode listTwo = ListOperate.createList(new int[]{1, 2, 3, 4, 5});
        //act
        ListNode result = ListOperate.reverseListWithStack(listOne);
        ListNode doubleResult = ListOperate.reverseListWithDoublePointer(listTwo);
        //verify
        ListNode expect = ListOperate.createList(new int[]{5, 4, 3, 2, 1});
        Assert.assertEquals(expect, result);
        Assert.assertEquals(expect, doubleResult);
    }
}