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;
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.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指针域为空),所以我们可以使用这个思路,完成对链表的反转

实现代码如下
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
|
public static Node reverse(Node head) { if(head == null || head.next == null) { return head; } Node reverseNode = reverse(head.next); head.next.next = head; 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();
|

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
|
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.next; } if(list1.head == null) { cur.next = list2.head; } if(list2.head == null) { cur.next = list1.head; } 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();
|

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
|
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));
|
