目录
1.反转链表
2.链表的中间节点
3.找到倒数第 k 个节点
4.分割链表
5.删除链表中的重复节点
6.判断回文链表
7.判断链表是否有环
8.一个环形链表，返回链表开始入环的第一个节点
9.找两个链表相交的节点
10.合并两个顺序链表
1.反转链表
反转链表我们先从前面开始反转，一个一个节点来
public ListNode reverseList() {
if(this.head == null) {
return null;
}
ListNode cur = this.head;
ListNode prev = null ;
ListNode curNext = cur.next;
while (cur != null) {
cur.next = prev;
prev = cur;
cur = curNext;
curNext = cur.next;
}
return prev;
}2.链表的中间节点
定义一个快慢指针来走，快的指针走的路程比慢的多一倍，所以慢指针指向的就是中间节点。
如果链表节点数是双数则返回第二个中间节点，如下所示
public ListNode middleNode() {
if(this.head == null) {
return null;
}
ListNode fast = this.head;
ListNode slow =this.head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}3.找到倒数第 k 个节点
public ListNode FindKthToTail(int k) {
if(k <= 0 || head ==null) {
return null;
}
ListNode fast = this.head;
ListNode slow = this.head;
while(k-1 != 0) {
fast = fast.next;
//fast == null是防止求的倒数第k个数超出节点长度，
if(fast == null) {
return null;
}
k--;
}
while(fast.next != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}4.分割链表
分割链表。给你一个链表的头节点 head 和一个特定值 x ， 使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
public ListNode partition(int x) {
ListNode bs = null;
ListNode be = null;
ListNode as = null;
ListNode ae = null;
ListNode cur = head;
while (cur != null) {
if(cur.val < x) {
//第一次
if(bs == null) {
bs = cur;
be = cur;
}else {
//不是第一次
be.next = cur;
be = be.next;
}
}else {
//第一次
if(as == null) {
as = cur;
ae = cur;
}else {
ae.next = cur;
ae = ae.next;
}
}
cur = cur.next;
}
//预防第一段为空
if(bs == null) {
return as;
}
be.next = as;
//预防最后一个节点的next域不为空
if(as != null) {
ae.next = null;
}
return bs;
}5.删除链表中的重复节点
升序排列的链表，删除多余重复的元素，使每个元素 只出现一次
public ListNode deleteDuplication() {
ListNode cur = head;
ListNode newHead = new ListNode(-1);
ListNode tmp = newHead;
while (cur != null) {
if(cur.next != null && cur.val == cur.next.val) {
//写while循环是防止有两个以上相同的
while (cur.next != null && cur.val == cur.next.val) {
cur = cur.next;
}
// cur = cur.next;//这一步是删完相同的节点，不留下一个
}else {
tmp.next = cur;
tmp = tmp.next;
cur = cur.next;
}
}
tmp.next = null;
return newHead.next;
}6.判断回文链表
public boolean isPalindrome() {
ListNode prev = head;
ListNode fast = head;
ListNode slow = head;
//1.slow找到了中间位置
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
//2.反转后半部分
ListNode cur = slow.next;
while (cur != null) {
ListNode curNext = cur.next;
cur.next = slow;
slow = cur;
cur = curNext;
}
//3.两边往中间走，判断回文
while (prev != slow) {
if(slow.val != prev.val) {
return false;
}
if(prev.next == slow) {
return true;
}
slow = slow.next;
prev = prev.next;
}
return true;
}
7.判断链表是否有环
public boolean hasCycle() {
if(head == null) return false;
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
return true;
}
}
return false;
}
8.一个环形链表，返回链表开始入环的第一个节点
public ListNode detectCycle(ListNode head) {
if(head == null) return null;
ListNode fast = head;
ListNode slow = head;
//判断是否有环
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
break;//相遇退出循环
}
}
if (fast == null || fast.next == null) {
return null;
}
//头和相遇点到环的入口点距离相等
fast = head;
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
return fast;
}9.找两个链表相交的节点
两个链表相交，及next 域相同
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null) {
return null;
}
ListNode pl = headA;
ListNode ps = headB;
int lenA = 0;
int lenB = 0;
while (pl != null) {
lenA++;
pl = pl.next;
}
pl = headA;
while (ps != null) {
lenB++;
ps = ps.next;
}
ps = headB;
int len = lenA - lenB;
if(len < 0) {
pl = headB;
ps = headA;
len = lenB - lenA;
}
//pl走差值len步
while (len != 0) {
pl = pl.next;
len--;
}
//同时走，直到相遇
while (pl != ps) {
pl = pl.next;
ps = ps.next;
}
//返回相遇的节点
return pl;//有值就返回值，是空就返回空。
}10.合并两个顺序链表
public static ListNode mergeTwoLists(ListNode headA,ListNode headB) {
ListNode newHead = new ListNode(-1);
ListNode tmp = newHead;
while(headA != null && headB != null) {
if(headA.val < headB.val) {
tmp.next = headA;
headA = headA.next;
tmp = tmp.next;
}else {
tmp.next = headB;
headB = headB.next;
tmp = tmp.next;
}
}
if(headA != null) {
tmp.next = headA;
}
if(headB != null) {
tmp.next = headB;
}
return newHead.next;
}