算法练习——链表

文章目录
  1. 1. 单链表的创建和删除
  2. 2. 从尾到头打印单链表
    1. 2.1. 栈实现
    2. 2.2. 递归实现
    3. 2.3. 区别
  3. 3. 在O(1)时间删除单链表节点
  4. 4. 链表中倒数第k个节点
  5. 5. 反转链表
  6. 6. 合并两个有序的链表
  7. 7. 两个链表的第一个公共点

单链表的创建和删除

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
95
96
97
98
99
100
101
import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.ToString;

/**
 * LinkList java单向链表实现及基础操作
 * Created by larry.su on 2017/4/3.
 */
@ToString
public class LinkList<E> {

    transient int size = 0;

    /**
     * 指向头结点
     */
    transient Node<E> first;
    /**
     * 指向尾节点
     * 需要根据尾节点操作时就不用每次都从头结点循环得到尾节点
     */
    transient Node<E> last;

    /**
     * 添加元素到链表尾端
     *
     * @param value 添加的数据
     */
    public void addToTail(E value) {
        Node node = new Node(value, null);

        //        if (null == first) {
//            first = node;
//        } else {
//            Node pNode = first;
//
//            while (null != pNode.next) {
//                pNode = pNode.next;
//            }
//
//            pNode.next = node;
//        }
        if (null == first) {
            first = node;
            last = node;
        } else {
            last.next = node;
            last = node;//使用last 可以减少循环获取最后节点步骤
        }
        size++;
    }

    /**
     * 删除第一个含有该值的节点
     *
     * @param object
     */
    public void remove(Object object) {
        if (null != first) {
            if (first.getValue().equals(object)) {
                first.next = null;
                first.value = null;
                size--;
            }

            Node preDeleteNode = first;//待删除的前一个节点
            Node deleteNode;//待删除的节点
            while (preDeleteNode.next != null) {
                if (preDeleteNode.next.getValue() == object) {
                    deleteNode = preDeleteNode.next;
                    preDeleteNode.next = deleteNode.next;
                    deleteNode.next = null;
                    deleteNode.value = null;
                    size--;
                } else {
                    preDeleteNode = preDeleteNode.getNext();
                }
            }
        }
    }

    @AllArgsConstructor
    @ToString
    @Data
    class Node<E> {
        E value;
        Node next;
    }

    public static void main(String[] args) {
        LinkList linkList = new LinkList();
        for (int i = 0; i < 6; i++) {
            linkList.addToTail(i);
        }

        linkList.remove(5);
        System.out.println(linkList);
        linkList.remove(3);
        System.out.println(linkList);
    }
}

结果：

1
2
LinkList(size=6, first=LinkList.Node(value=0, next=LinkList.Node(value=1, next=LinkList.Node(value=2, next=LinkList.Node(value=3, next=LinkList.Node(value=4, next=null))))), last=LinkList.Node(value=null, next=null))
LinkList(size=6, first=LinkList.Node(value=0, next=LinkList.Node(value=1, next=LinkList.Node(value=2, next=LinkList.Node(value=4, next=null)))), last=LinkList.Node(value=null, next=null))

从尾到头打印单链表

栈实现

遍历的顺序是从头到尾的顺序，输出的顺序是从尾到头，也就是说第一个遍历的节点最后一个输出，这个是典型的『后进先出』。可以使用栈实现这种顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
     * 使用栈的方式反向输出单链表
     *
     * @param linkList 单向链表
     */
    private static void printListByStack(LinkList linkList) {
        if (linkList.first != null) {
            LinkList.Node node = linkList.first;
            Stack<LinkList.Node> stack = new Stack<LinkList.Node>();
            while (node != null) {
                stack.push(node);
                node = node.next;
            }

            while (stack.size() > 0) {
                LinkList.Node node2 = stack.pop();
                System.out.print(node2.getValue() + " ");
            }
        }
    }

递归实现

既然想到了栈实现，而递归本质上也是个栈结构。要实现反过来输出链表，我们每访问到一个节点的时候，先递归输出他后面的节点，再输出该节点自身。

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * 递归方式反向输出单链表
 *
 * @param node 单向链表中的节点
 */
public static void printListByRecursion(LinkList.Node node) {
    if (null != node) {
        if (null != node.next) {
            printListByRecursion(node.next);
        }
        System.out.print(node.getValue() + " ");
    }
}

区别

递归的代码看起来简洁，但是有个问题，当链表非常长的时候，就会导致函数调用层级很深，从而导致栈溢出。基于栈实现的代码鲁棒性更好一些。

我们来测试下两种方式的性能及异常，测试代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void testProfile(int size){
    LinkList linkList = new LinkList();
    for (int i = 0; i < size; i++) {
        linkList.addToTail(i);
    }

    Profiler.begin();
    printListByStack(linkList);
    System.out.println("========");
    System.out.println("Stack Cost: " + Profiler.end() + " mills");

    Profiler.begin();
    printListByRecursion(linkList.first);
    System.out.println("========");
    System.out.println("Rescursion Cost: " + Profiler.end() + " mills");
}

首先测试下10000个节点的单链表反向输出，结果如下：

1
2
Stack Cost: 30 mills
Rescursion Cost: 47 mills

再测试下50000个：

1
2
3
Stack Cost: 117 mills

Exception in thread "main" java.lang.StackOverflowError

可以看到，性能上使用栈反向输出要更好一些，当节点过多时，使用递归的方式会导致栈溢出。

在O(1)时间删除单链表节点

给定单向链表的头节点和一个节点，定义一个函数在O(1)时间删除该节点。

最常规的做法无疑是从链表的头结点开始，顺序遍历查找要删除的节点，并在链表中删除该节点。但是这种时间复杂度为O(n)。

O(1)的解决方法为：把待删除节点（假设为C）的下一个节点（D）的内容复制到该节点上，覆盖原有的内容，然后将待删除的下一个节点（D）删除即可。

需要注意的是：（1）若待删除的节点为尾节点，则需要顺序遍历链表得到待删除节点的前序节点，然后删除尾节点；（2）若待删除的节点为头节点，则删除头节点。代码如下：

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
/**
    * 在O(1)时间删除单链表节点
    * @param first 头节点
    * @param toBeDelete 待删除节点
    * @return 返回删除的节点内容
    */

   String deleteNode(LinkList.Node first, LinkList.Node toBeDelete) {
       String returnValue = "";
       //链表只有一个节点
       if (toBeDelete.next == first.next) {
           returnValue = first.value.toString();//待删除节点的内容
           first.value = null;
           return  returnValue;
       }

       //待删除节点不是尾节点
       if(null != toBeDelete.next){
           LinkList.Node toBeDeleteNext = toBeDelete.next;
           toBeDelete.value = toBeDeleteNext.value;
           toBeDelete.next = toBeDeleteNext.next;

           returnValue = toBeDeleteNext.value.toString();//待删除节点的下一个节点的内容

           toBeDeleteNext.value = null;
           toBeDeleteNext.next = null;

           return  returnValue;
       }

       //待删除节点为尾节点(顺序遍历链表得到待删除节点的前序节点)
       if(null == toBeDelete.next){
           LinkList.Node node = first;
           while (toBeDelete != node.next) {
               node = node.next;
           }

           returnValue = toBeDelete.value.toString();//待删除节点的内容

           toBeDelete.value = null;
           node.next = null;

           return  returnValue;
       }
       return  returnValue;
   }

测试用例如下：

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
@Test
public void deleteNodeTheFirstNode() throws Exception {
    LinkList linkList = generatorALinkList(1);
    DeleteNodeO1 deleteNode = new DeleteNodeO1();

    String returnValue = deleteNode.deleteNode(linkList.first,linkList.first);

    Assert.assertEquals("0",returnValue);//删除的是头节点
}

@Test
public void deleteNodeTheLastNode() throws Exception {
    LinkList linkList = generatorALinkList(9);
    DeleteNodeO1 deleteNode = new DeleteNodeO1();

    String returnValue = deleteNode.deleteNode(linkList.first,linkList.last);

    Assert.assertEquals("8",returnValue);//删除的是尾节点
}

@Test
public void deleteNodeNotFirstAndLastNode() throws Exception {
    LinkList linkList = generatorALinkList(9);
    DeleteNodeO1 deleteNode = new DeleteNodeO1();

    //删除第二个节点，将第三个节点内容（值为2）复制到第二个节点上，删除第三个节点
    String returnValue = deleteNode.deleteNode(linkList.first,linkList.first.next);

    Assert.assertEquals("2",returnValue);
}

private LinkList generatorALinkList(int size){
    LinkList linkList = new LinkList();
    for (int i = 0; i < size; i++) {
        linkList.addToTail(i);
    }
    return  linkList;
}

链表中倒数第k个节点

输入一个链表，输出该链表中倒数第K个节点。从1开始计数，例如一个链表6个节点，从头到尾的顺序为1，2，3，4，5，6。这个链表的倒数第3个节点是值为4的节点。

遍历2次的思路：第一次遍历获取整个链表的长度n，第二次遍历找到第k个节点n-k+1

遍历1次的思路：定义两个指针，第一个指针从链表头部开始遍历向前走k-1时，第二个指针不动；从第K步开始，第二个指针开始从链表头部遍历。两个指针距离保持在K-1，当第一个指针走到尾部的时候，第二个指针正好是倒数第K个节点。

一次遍历的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
LinkList.Node findNodeToTail(LinkList linkList, int k) {
        if (null == linkList || null == linkList.first || k == 0) {
            return null;
        }
        LinkList.Node ahead = linkList.first;
        LinkList.Node behind = linkList.first;

        for (int i = 0; i < k - 1; i++) {
            if (ahead.next != null) {
                ahead = ahead.next;
            } else {
                return null;
            }
        }

        while (ahead.next != null) {
            ahead = ahead.next;
            behind = behind.next;
        }

        return behind;
    }

单元测试：

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
@Test
public void findNodeToTail() throws Exception {//正常情况下，6个节点，倒数第3个
    FindToTail findToTail = new FindToTail();
    LinkList linkList = generatorALinkList(6);
    LinkList.Node node = findToTail.findNodeToTail(linkList,3);
    Assert.assertEquals(3,node.getValue());
}

@Test
public void findNodeToTailKEqual0() throws Exception {//k等于0
    FindToTail findToTail = new FindToTail();
    LinkList linkList = generatorALinkList(6);
    LinkList.Node node = findToTail.findNodeToTail(linkList,0);
    Assert.assertEquals(null,node);
}

@Test
public void findNodeToTailListIsNull() throws Exception {//单向链表null
    FindToTail findToTail = new FindToTail();
    LinkList.Node node = findToTail.findNodeToTail(null,1);
    Assert.assertEquals(null,node);
}

@Test
public void findNodeToTailListSize0() throws Exception {//只有头结点
    FindToTail findToTail = new FindToTail();
    LinkList linkList =  generatorALinkList(1);
    LinkList.Node node = findToTail.findNodeToTail(linkList,8);//链表节点总数少于k
    Assert.assertEquals(null,node);
}

反转链表

定义一个函数，输入一个链表的头结点，反转链表并输出反转后链表的头结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
LinkList.Node reverseAndPrintHead(LinkList.Node first) {
    LinkList.Node reverseHead = null;
    LinkList.Node node = first;//当前结点
    LinkList.Node prevNode = null;//当前结点的前结点

    while (node != null) {
        LinkList.Node nextNode = node.next;//当前结点的后结点

        if (nextNode == null) {
            reverseHead = node;
        } else {
            node.next = prevNode;//反转
            nextNode.next = node;//反转
        }
        node = nextNode;//下一个循环
    }

    return reverseHead;
}

单元测试：

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
@Test
public void reverseAndPrintHead() throws Exception {
    ReverseList reverse = new ReverseList();
    //链表有多个结点
    LinkList.Node node = reverse
            .reverseAndPrintHead(generatorALinkList(6).first);
    Assert.assertEquals(5,node.value);
}

@Test
public void reverseAndPrintHead1() throws Exception {
    ReverseList reverse = new ReverseList();
    //链表头节点为null
    LinkList.Node node = reverse
            .reverseAndPrintHead(generatorALinkList(0).first);
    Assert.assertEquals(null,node);
}

@Test
public void reverseAndPrintHead2() throws Exception {
    ReverseList reverse = new ReverseList();
    //链表只有一个节点
    LinkList.Node node = reverse
            .reverseAndPrintHead(generatorALinkList(1).first);
    Assert.assertEquals(0,node.value);
}

合并两个有序的链表

输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然按照递增顺序排序。

首先定义一个合并列表M，然后同时遍历2个链表L1,L2，比较相同位置结点（P1，P2）值大小，将小的节点（假设P1<P2,则P1）合并到M，然后将P1的下一个节点P1.next和P2节点值比较，递归上述步骤直到某个链表结束，另外一个链表多余的直接合并到M。

合并的时候，注意特殊情况：

  • L1空，直接返回L2
  • L2空，直接返回L1
  • L1，L2都空，返回空
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
LinkList.Node merge (LinkList.Node first1,LinkList.Node first2){

        if (null == first1) {
            return first2;
        }

        if (null == first2) {
            return first1;
        }

        LinkList.Node mergeFirst= null;
        if ((Integer.parseInt(first1.value.toString())
                < Integer.parseInt(first2.value.toString()))){
            mergeFirst = first1;
            mergeFirst.next = merge(first1.next,first2);
        } else {
            mergeFirst = first2;
            mergeFirst.next = merge(first1,first2.next);
        }

        return mergeFirst;
    }

单元测试：

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
@Test
    public void merge() throws Exception {
        LinkList list1 = generatorALinkList(4,20);
        LinkList list2 = generatorALinkList(5,30);

        MergeList mergeList = new MergeList();
        LinkList.Node mergeFirstNode = mergeList.merge(list1.first,list2.first);
        printList(mergeFirstNode);
        Assert.assertEquals(4,mergeFirstNode.value);

    }

    @Test
    public void merge2List1Null() throws Exception {
        LinkList list2 = generatorALinkList(5,16);

        MergeList mergeList = new MergeList();
        //lis1为null
        LinkList.Node mergeFirstNode = mergeList.merge(null,list2.first);

        Assert.assertEquals(5,mergeFirstNode.value);

    }

    @Test
    public void merge2List2Null() throws Exception {
        LinkList list1 = generatorALinkList(4,10);

        MergeList mergeList = new MergeList();
        //lis2为null
        LinkList.Node mergeFirstNode = mergeList.merge(list1.first,null);

        Assert.assertEquals(4,mergeFirstNode.value);

    }

    @Test
    public void merge2BothNull() throws Exception {
        MergeList mergeList = new MergeList();
        //都为null
        LinkList.Node mergeFirstNode = mergeList.merge(null,null);

        Assert.assertEquals(null,mergeFirstNode);

    }

    private LinkList generatorALinkList(int start,int max) {
        LinkList linkList = new LinkList();
        for (int i = start; i < max; i+=2) {
            linkList.addToTail(i);
        }
        return linkList;
    }

两个链表的第一个公共点

输入两个单链表，找出他们的第一个公共节点。