- [1、判断一个单链表是否有环]
可使用一快一慢两个指针，一个指针每次走一步，另一个指针一次走两步。若存在环，若干步后，快的指针会赶上慢的指针。否则则判定不存在环
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
static ListNode hasCircle(ListNode node) {
if (node == null)
return null;
ListNode resultNode = null;
ListNode slow = node.next;
if (slow == null)
return null;
ListNode fast = slow.next;
while (fast != null && slow != null) {
if (fast == slow) {
resultNode = fast;
break;
}
slow = slow.next;
fast = fast.next;
if (fast != null) {
fast = fast.next;
}
}
return resultNode ;
}
- [2判断一个单链表中环的入口节点]
首先使用1中方法判断链表中是否有环，获取环中任意一个节点，然后得到环的长度为n。
然后定义两个指针，一个指针先走n步，然后两个指针在以相同的速度移动，当第二个指针走到入口节点时，第一个指针刚好走了一圈，也到达入口节点，这时就找到了环的入口节点。
static ListNode getEntryNode(ListNode node) {
ListNode meetingNode = hasCircle(node);
if (meetingNode == null)
return null;
int loopNum = 1;
ListNode pNode1 = meetingNode;
while (pNode1.next != meetingNode) {
pNode1 = pNode1.next;
++loopNum;
}
pNode1 = node;
for (int i = 0; i < loopNum; i++) {
pNode1 = pNode1.next;
}
ListNode pNode2 = node;
while (pNode1 != pNode2) {
pNode1 = pNode1.next;
pNode2 = pNode2.next;
}
return pNode1;
}
//返回头指针
static ListNode insertNode(ListNode node, int k, int num) {
ListNode kNode = new ListNode(num);
if (node == null)
node = new ListNode(num);
int i = 0;
ListNode preNode = node;
while (preNode != null && i < k - 1) {
if (++i == k - 1)
break;
preNode = preNode.next;
}
if ((k - 1) != i) {// 插入位置不合法
return node;
}
if (k == 1) {// 插入首位
kNode.next = node;
node = kNode;
} else {
// 中间节点或尾结点
kNode.next = preNode.next;
preNode.next = kNode;
}
return node;
}
-
4找到单链表中的倒数第k个位置的结点
设链表长为n，从后往前查第k个结点即从前往后找的第n-k+1个结点。这时可以使用两个指针，第一个指针先走k-1步，第k步时，两个指针同时往前走，因为两个指针始终相差k-1，所以当第一个指针到达链表终点时，第二个指针刚好到达n-k+1个结点，即倒数第k个结点。
static ListNode getKNode(ListNode node, int k) {
ListNode pHead = node;
ListNode pBehind = node;
for (int i = 0; i < k - 1; i++) {
pHead = pHead.next;
}
while (pHead.next != null) {
pHead = pHead.next;
pBehind = pBehind.next;
}
return pBehind;
}
public static ListNode reverseNode(ListNode node) {
if (node == null)
return null;
ListNode reverseNode = null;
ListNode head = node;
ListNode preNode = null;
while (head != null) {
ListNode nextNode = head.next;
if (nextNode == null)
reverseNode = head;
head.next = preNode;
preNode = head;
head = nextNode;
}
return reverseNode;
}
public static ListNode delete(ListNode node, int data) {
if (node == null)
return null;
//现将链表头部的值为data的数据删除
while (node != null) {
if (node.val == data)
node = node.next;
else break;
}
ListNode preNode = null;//要删除的节点的前一个结点
ListNode temp = node;//返回链表，先指向头结点
ListNode head = node;//遍历指针
while (head != null) {
if (head.val != data) {
preNode = head;
} else {
preNode.next = preNode.next.next;
}
head = head.next;
}
return temp;
}
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode node = new ListNode(0) , temp = node;
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;
}
temp.next = (l1!=null)?l1:l2; //若l1为null,则temp指向l2,否者指向l1
return node.next;
}
}
