1.单链表反转（LeetCode 206）
//非递归解法
public ListNode reverseList(ListNode head) {
//长度为0或1直接返回
if (head == null || head.next == null) {
return head;
}
ListNode currNode = head;
ListNode preNode = null;
//临时变量存储下一个
ListNode nextTemp = null;
while (currNode != null) {
nextTemp = currNode.next;
currNode.next = preNode;
preNode = currNode;
currNode = nextTemp;
}
return preNode;
}
2.链表中环的检测 (LeetCode 141)
//典型的快慢指针的思想。
//除此之外，当换不是无限大的时候我们也可以用死循环来判断有没有环，循环一段时间，看看next是不是为null.
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head;
while (slow != null && fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}
return false;
}
3.求链表中环开始结点 (LeetCode 142)
解题思路：
1.首先通过快慢指针的方法判断链表是否有环；
2.接下来如果有环，则寻找入环的第一个节点。具体的方法为，首先假定链表起点到入环的第一个节点A的长度为a【未知】，到快慢指针相遇的节点B的长度为（a + b）【这个长度是已知的】。现在我们想知道a的值，注意到快指针fast始终是慢指针slow走过长度的2倍，所以慢指针slow从B继续走（a + b）又能回到B点，如果只走a个长度就能回到节点A。但是a的值是不知道的，解决思路是曲线救国，注意到起点到A的长度是a，那么可以用一个从起点开始的新指针result和从节点B开始的慢指针slow同步走，相遇的地方必然是入环的第一个节点A。 文字有点绕，画个图就一目了然了.
public static ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
ListNode result = head;
boolean hasCycle = false;
while (fast != null && fast.next != null && slow != null) {
fast = fast.next.next;
slow = slow.next;
//判断是否有环
if (slow == fast) {
hasCycle = true;
break;
}
}
if (hasCycle) {
while (result != slow) {
result = result.next;
slow = slow.next;
}
return result;
}
return null;
}
4.两个有序链表合并 (LeetCode 21)
public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null || l2 == null) {
return l1 == null ? l2 : l1;
}
ListNode temp = new ListNode(0);
ListNode result = temp;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
temp.next = l1;
l1 = l1.next;
} else {
temp.next = l2;
l2 = l2.next;
}
temp = temp.next;
}
//如果l1或者l2任何一个为空，就将另一个直接接在尾部。
if (l1 == null) {
temp.next = l2;
} else {
temp.next = l1;
}
return result.next;
}
5.删除链表的倒数第N个结点 (LeetCode 19)
//解法一，两次遍历。正常的思维是先求出链表的长度，然后从头到尾去遍历。
public static ListNode removeLastN(ListNode head, int n) {
int len = 0;
ListNode point = head;
//遍历链表得出总长度
while (point != null) {
point = point.next;
len++;
}
//得到是删除正数第几个
int k = len - n;
//指针，指向head
ListNode point2 = new ListNode(0);
ListNode result = point2;
point2.next = head;
//前面的照常遍历
for (int i = 0; i <= k; i++) {
point2 = point2.next;
}
//第K个就删除
point2.next = point2.next.next;
return result.next;
}
//解法二，一次遍历。这一种解法是利用了快慢指针，一般情况下不太容易想出此种方法。
public static ListNode onceRemoveLastN(ListNode head, int n) {
//慢指针
ListNode slow = new ListNode(-1);
slow.next = head;
ListNode result = slow;
//快指针
ListNode fast = new ListNode(-1);
fast.next = head;
while (fast != null) {
fast = fast.next;
//快指针先走n步
if (n < 0) {
slow = slow.next;
}
n--;
}
slow.next = slow.next.next;
return result.next;
}
关于删除链表结点的问题：
- 链表的头和尾这两个结点比较特殊，删除的时候要考虑边界情况。一般我们是用一个指针的next指向这个链表的头。这样头部的特殊情况就可以解决。
- 关于一个结点node的删除我们一般有两种做法：
//方法一：
preNode.next = preNode.next.next; //preNode为node的前面一个结点
//方法二：
node.val = node.next.val;
node.next = node.next.next;
同样，这两种方法要考虑边界情况。
6.求链表的中间结点 (N等分点)
//二等分代码
public static ListNode halfNode(ListNode head) {
ListNode fast = new ListNode(0);
fast.next = head;
ListNode slow = new ListNode(0);
slow.next = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
如果是N等分的话也是用快慢指针的思想，快指针一次性走N步，慢指针一次走一步，最后快指针走到终点的时候，慢指针所在的结点就是N等分点（注意验证一些边界情况)。
网友评论