1、使用java实现单链表

建立Node节点类的代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Node {
    Integer data;
    Node next;

    public Node(Integer data) {
        this.data = data;
    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                '}';
    }
}

建立链表类并编写链表类的添加节点和遍历方法

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
public class LinkedList {
    Node head;
    
    /***
     * 添加节点的方法
     * @param node 待添加节点
     */
    public void addNode(Node node) {
        if(this.head == null) {
            //如果当前头节点为空，那么将传入的节点作为头节点
            this.head = node;
            return;
        }
        //由于单链表的头节点不可移动，所以我们使用一个临时指针来辅助我们添加节点。
        Node temp = head;
        while(true) {
            if(temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        //退出循环时，temp节点指向链表最后一个节点，此时将传入节点挂在temp之后即可
        temp.next = node;
    }

    /***
     * 遍历链表的方法
     */
    public void list() {
        if(this.head == null) {
            System.out.println("链表为空，无法遍历！");
            return;
        }
        Node temp = head;
        while(true) {
            if(temp == null) {
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }
}

2、编写代码实现单链表的反转

这里使用递归来完成单链表的反转，这个算法的思路大体如下

  • 假设现在有一条单链表：1-2-3-4-NULL，在每次进入倒置函数reverse之前，需要对传入的节点进行判断，当传入的节点为空或者传入节点的next指针域为空时，证明该链表不需要反转，直接返回该节点。
  • 当传入节点的指针域不为空时，将该节点的下一个节点的next域指向自己，同时将该节点的next指针域置为空，这样就形成了局部意义上的链表节点反转，由于我们使用了递归，并设置了递归退出条件（当前传入节点为空或者当前传入节点的next指针域为空），所以我们可以使用这个思路，完成对链表的反转

image-20210129152444803

实现代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/***
 * 
 * @param head
 * @return
 */
public static Node reverse(Node head) {
    if(head == null || head.next == null) {
        //如果进入这个if块中，证明当前head与其之后结点形成的链表不需要反转
        //例如1-2-3-4中的4不需要反转，直接返回该节点即可
        return head;
    }
    //如果链表长度大于等于2，进行递归
    Node reverseNode = reverse(head.next);
    //将当前节点下一个节点的next指针域指向自己
    head.next.next = head;
    //将当前节点的next指针域置空
    head.next = null;
    return reverseNode;
}

创建一个链表：1-2-3-4-5，测试代码与结果如下

1
2
3
4
5
6
7
8
9
LinkedList linkedList = new LinkedList();
for (int i = 0; i < 5; i++) {
    linkedList.addNode(new Node(i + 1));
}
System.out.println("反转前:");
linkedList.list();
LinkedList reverseList = new LinkedList(reverse(linkedList.head));
System.out.println("反转后:");
reverseList.list();
  • 结果

image-20210129152457748

3、将两个有序单链表合并为一个有序单链表

将A链表：1-2-3-null与B链表2-3-6-null合并为一张有序链表，解题思路如下

  • 新建一个链表temp，然后使用指针遍历AB链表，对每一次遍历出来的节点的data值进行比较，将data值较小的节点从原链表中摘除，然后加到temp链表中，直到有一条链表被摘空。
  • 此时如果A链表被摘空，那么将B链表剩余的节点挂在temp节点的最后面，由于B链表和temp链表本来就是有序的，所以得出的结果仍然是一个有序列表，反之亦然。

代码实现

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
/***
 * 合并两个有序链表
 * @param list1 链表1
 * @param list2 链表2
 * @return
 */
public static LinkedList mergeTwoList(LinkedList list1,LinkedList list2) {
    //创建一个
    LinkedList temp = new LinkedList(new Node(Integer.MIN_VALUE));
    Node cur = temp.head;
    while(list1.head != null && list2.head != null) {
        if(list1.head.data < list2.head.data) {
            cur.next = list1.head;
            list1.head = list1.head.next;
        } else {
            cur.next = list2.head;
            list2.head = list2.head.next;
        }
        //每一次循环后都需要将cur后移
        cur = cur.next;
    }
    //退出循环时，至少有一个链表为空
    //如果是第一个链表为空，那么将cur.next指向第二个链表的头节点，由于第二个链表本身就是有序的，所以合并后仍然有序
    if(list1.head == null) {
        cur.next = list2.head;
    }
    if(list2.head == null) {
        cur.next = list1.head;
    }
    //由于temp的第一个节点为MIN_VALUE，为无效节点，所以返回下一个
    return new LinkedList(temp.head.next);
}

测试代码及结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
LinkedList list1 = new LinkedList();
list1.addNode(new Node(1));
list1.addNode(new Node(2));
list1.addNode(new Node(4));
System.out.println("链表1为:");
list1.list();

LinkedList list2 = new LinkedList();
list2.addNode(new Node(1));
list2.addNode(new Node(3));
list2.addNode(new Node(4));
System.out.println("链表2为:");
list2.list();

LinkedList result = mergeTwoList(list1,list2);
System.out.println("合并结果为:");
result.list();
  • 结果

image-20210129152513991

4、返回链表中倒数第K个结点

返回链表倒数第K个结点，结题思路如下

  • 创建两个指针before和after，并将其指向链表头节点head
  • 先让after结点前进k步，如果在此过程中after结点已经走出链表的范围（即移动过程中after已为空），那么证明输入的k不合法，此时返回null。
  • 完成上一步的操作后，进行循环并使before和after同时进行移动，直到after为空时退出循环，此时before指向的元素即为链表的倒数第k个结点。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/***
 * 获取链表的倒数第k个结点
 * @param list 链表
 * @param k
 * @return
 */
public static Node getKthFromEnd(LinkedList list,int k) {
    if(list.head == null || list == null || k < 0) {
        return null;
    }
    Node before = list.head;
    Node after = list.head;
    for (int i = 0;i < k;i++) {
        if(after == null) {
            return null;
        }
        after = after.next;
    }
    while(after != null) {
        before = before.next;
        after = after.next;
    }
    return before;
}

测试代码以及结果，这里的链表使用上面合并链表的结果

1
2
3
4
5
LinkedList result = mergeTwoList(list1,list2);
System.out.println("合并结果为:");
result.list();

System.out.println("倒数第3个结点值为:" + getKthFromEnd(result,2));
  • 结果

image-20210129152527059