Skip to main content

链表

public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}

删除节点

public void deleteNode(ListNode node) {
if (node.next == null){
node = null;
return;
}
// 取缔下一节点
node.val = node.next.val
node.next = node.next.next
}

翻转链表

public ListNode reverse(ListNode head) {
//prev表示前继节点
ListNode prev = null;
while (head != null) {
//temp记录下一个节点,head是当前节点
ListNode temp = head.next;
head.next = prev;
prev = head;
head = temp;
}
return prev;
}

中间元素

public ListNode findMiddle(ListNode head){
if(head == null){
return null;
}

ListNode slow = head;
ListNode fast = head;

// fast.next = null 表示 fast 是链表的尾节点
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
return slow;
}

判断是否为循环链表

public Boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}

ListNode slow = head;
ListNode fast = head.next;

while (fast != slow) {
if(fast == null || fast.next == null) {
return false;
}
fast = fast.next.next;
slow = slow.next;
}
return true;
}

合并两个已排序链表

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode lastNode = dummy;

while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
lastNode.next = l1;
l1 = l1.next;
} else {
lastNode.next = l2;
l2 = l2.next;
}
lastNode = lastNode.next;
}

if (l1 != null) {
lastNode.next = l1;
} else {
lastNode.next = l2;
}

return dummy.next;
}

链表排序

可利用归并、快排等算法实现

// 归并排序
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}

ListNode mid = findMiddle(head);

ListNode right = sortList(mid.next);
mid.next = null;
ListNode left = sortList(head);

return mergeTwoLists(left, right);
}

// 快速排序
public ListNode sortList(ListNode head) {
quickSort(head, null);
return head;
}

private void quickSort(ListNode start, ListNode end) {
if (start == end) {
return;
}

ListNode pt = partition(start, end);
quickSort(start, pt);
quickSort(pt.next, end);
}

private ListNode partition(ListNode start, ListNode end) {
int pivotKey = start.val;
ListNode p1 = start, p2 = start.next;
while (p2 != end) {
if (p2.val < pivotKey) {
p1 = p1.next;
swapValue(p1, p2);
}
p2 = p2.next;
}

swapValue(start, p1);
return p1;
}

private void swapValue(ListNode node1, ListNode node2) {
int tmp = node1.val;
node1.val = node2.val;
node2.val = tmp;
}

删除倒数第N个节点

public ListNode removeNthFromEnd(ListNode head, int n) {
if (n <= 0) {
return null;
}

ListNode dummy = new ListNode(0);
dummy.next = head;

ListNode preDelete = dummy;
for (int i = 0; i < n; i++) {
if (head == null) {
return null;
}
head = head.next;
}
// 此时head为正数第N个节点
while (head != null) {
head = head.next;
preDelete = preDelete.next;
}
preDelete.next = preDelete.next.next;
return dummy.next;
}

两个链表是否相交

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}

ListNode currA = headA;
ListNode currB = headB;
int lengthA = 0;
int lengthB = 0;

// 让长的先走到剩余长度和短的一样
while (currA != null) {
currA = currA.next;
lengthA++;
}
while (currB != null) {
currB = currB.next;
lengthB++;
}

currA = headA;
currB = headB;
while (lengthA > lengthB) {
currA = currA.next;
lengthA--;
}
while (lengthB > lengthA) {
currB = currB.next;
lengthB--;
}

// 然后同时走到第一个相同的地方
while (currA != currB) {
currA = currA.next;
currB = currB.next;
}
// 返回交叉开始的节点
return currA;
}