我们在这篇文章主要记录下链表的基本操作. 主要包括
- 反转链表
- 检测环
- 两个有序的链表合并
- 删除倒数第K个节点
- 求链表的中间结点
首先定义单向链表, 数据包含整型的变量和下一个节点的指针.
public static class Node {
private int data;
private Node next;
public Node(int data, Node next) {
this.data = data;
this.next = next;
}
public int getData() {
return data;
}
}
定义print方法,顺序打印链表的值.验证结果的正确性.
public static void print(Node list) {
while (list != null) {
System.out.print(list.data);
list = list.next;
}
System.out.println("======================");
}
一. 反转链表
链表前进的过程中记录下前一个节点的指针. 同时改变当前节点的指针. 使当前节点指向前一个节点.最后返回反转后的链表. 我练习的时候,犯了一个错误. 我想用同一个变量表示反转前, 反转后的链表. 但是这样是行不通的. 因为这里面list传递过来的是一个引用. 而我再list.next = prev; 这一行代码把list的内在属性改变了. 相当于list.next =null; list没有下一个节点了. list 中只有头结点的数据. 这里需要注意.
/**
* 反转链表
*
* @param list 入参链表
* @return 反转链表
*/
public static Node reverse(Node list) {
Node prev = null;
Node current = list;
Node head = null;
while (current != null) {
Node next = current.next;
current.next = prev;
prev = current;
if (next == null) {
head = current;
}
current = next;
}
return head;
}
@Test
public void reverseTest() {
Node head = new Node(1, null);
head.next = new Node(2, null);
print(head);
Node rNode = reverse(head);
System.out.println("++++反转链表+++");
print(rNode);
}
二 . 检测环
使用快慢指针操作. 快指针一次走两步. 慢指针一次走一步. 如果存在环. 那么就会存在扣圈的情况. 终将相遇.
这里注意处理边界条件即可
/**
* 检测链表中是否存在环
*
* @param head
* @return
*/
private boolean checkCircle(Node head) {
if (head == null) {
return false;
}
Node fast = head;
Node slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
return true;
}
}
return false;
}
@Test
public void checkCircleTest() {
Node one = new Node(1, null);
Node two = new Node(2, null);
Node three = new Node(3, null);
Node four = new Node(4, null);
one.next = two;
two.next = three;
three.next = four;
four.next = two;
boolean hasCircle = checkCircle(one);
System.out.println(hasCircle);
}
三. 两个有序的链表合并
面试有碰到过问两个有序数组合并的情况. 和这种应该类似. 就是首先比较两个链表中第一个元素的值. 把较小节点的作为新链表的头结点.移动节点到下一个位置. 然后在循环体中比较. 较小的放到新链表中. 并移动到下一个节点的位置. 最后考虑一种情况. 有可能一个链表已经移动到尾节点. 这时候把另外一个链表剩余的那部分节点.添加到新链表. 并返回新链表.
**
* 合并两个有序链表
*
* @param list1 链表1
* @param list2 链表2
* @return 合并后的链表
*/
private Node merge(Node list1, Node list2) {
Node head;
if (list1 == null) {
return list2;
}
if (list2 == null) {
return list1;
}
if (list1.data < list2.data) {
head = list1;
list1 = list1.next;
} else {
head = list2;
list2 = list2.next;
}
Node current = head;
while (list1 != null && list2 != null) {
if (list1.data < list2.data) {
current.next = list1;
list1 = list1.next;
} else {
current.next = list2;
list2 = list2.next;
}
current = current.next;
}
if (list1 != null) {
current.next = list1;
} else {
current.next = list2;
}
return head;
}
@Test
public void mergeTest() {
Node one = new Node(1, null);
Node two = new Node(2, null);
Node three = new Node(3, null);
Node four = new Node(4, null);
Node five = new Node(5, null);
one.next = three;
three.next = five;
two.next = four;
Node list1 = one;
Node list2 = two;
print(list1);
print(list2);
Node mergeList = merge(list1, list2);
print(mergeList);
}
四. 删除倒数第K个节点
我先跑,如果你能追上我. 我就跟你嘿嘿嘿. 就是这么骚气. 我怎么知道倒数第K个节点. 这里也是用两个指针. fast 指针先跑K个单位. slow这时候开始跑. fast跑到结尾的时候. slow此时的位置恰好就是倒数第K个位置.
这就把问题转化成小学数学题了.
/**
* 删除倒数第k个数据
*
* @param list
* @param k
*/
private Node deleteLastKTest(Node list, int k) {
int i = 1;
Node slow = list;
Node fast = list;
while (fast != null && i < k) {
fast = fast.next;
i++;
}
if (fast == null) {
return list;
}
Node pre = null;
while (fast.next != null) {
fast = fast.next;
pre = slow;
slow = slow.next;
}
if (pre == null) {
list = list.next;
} else {
pre.next = pre.next.next;
}
return list;
}
@Test
public void deleteLastKTest() {
Node one = new Node(1, null);
Node two = new Node(2, null);
Node three = new Node(3, null);
Node four = new Node(4, null);
Node five = new Node(5, null);
one.next = two;
two.next = three;
three.next = four;
four.next = five;
int k = 5;
Node node = deleteLastKTest(one, k);
print(node);
}
五. 求链表的中间结点
快慢指针. 一个二倍速fast. 一个一倍速slow. fast 走到结尾. slow恰好走一半.
/**
* 返回中间节点
* @param list
* @return
*/
private Node middleNode(Node list) {
if(list==null){
return null;
}
Node fast = list;
Node slow = list;
while(fast.next!=null && fast.next.next!=null){
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
@Test
public void middleNodeTest() {
Node one = new Node(1, null);
Node two = new Node(2, null);
Node three = new Node(3, null);
Node four = new Node(4, null);
Node five = new Node(5, null);
Node six = new Node(6,null);
one.next = two;
two.next = three;
three.next = four;
four.next = five;
five.next = six;
Node node = middleNode(one);
System.out.println(node.data);
}
网友评论