无头单链表 现场手撕代码+分析,供自己闲时手机复习使用!
- 删除链表中等于给定值 val 的所有节点。
- 反转一个单链表。
- 给定一个带有头结点 head 的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。
- 输入一个链表,输出该链表中倒数第k个结点。
- 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
- 编写代码,以给定值x为基准将链表分割成两部分,所有小于x的结点排在大于或等于x的结点之前 。
- 在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。
- 链表的回文结构。
- 输入两个链表,找出它们的第一个公共结点。
- 给定一个链表,判断链表中是否有环。
- 给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 NULL
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
}
}
public class Ex01 {
/*1.反转一个单链表*/
public Node reverseList(Node head) {
if (head == null) {
return null;
}
if (head.next == null) {
return head;
}
Node newHead = null;
Node prev = null;
Node cur = head;
while (cur != null) {
Node curNext = cur.next;
if (curNext == null) {
newHead = cur;
}
cur.next = prev;
prev = cur;
cur = curNext;
}
return newHead;
}
/*2.删除指定元素*/
public Node remover(Node head, int val) {
if (head == null) {
return null;
}
Node cur = head;
Node next = head.next;
while (cur.next != null) {
if (cur.next.data == val) {
cur.next = next.next;
} else {
cur = cur.next;
}
}
if (head.data == val) {
head = head.next;
}
return head;
}
/*3.返回单链表的中间结点,如果有两个返回第二个结点*/
public Node middleNode(Node head) {
if (head == null) {
return null;
}
Node fast = head;
Node slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
/*
int len = size(head) / 2;
Node cur = head;
for (int i = 0; i < len; i++) {
cur = cur.next;
}
return cur;*/
}
/*4.返回倒数第K个结点*/
public Node findKthToTail(Node head, int k) {
if (k == 0 || head == null) {
return null;
}
Node fast = head;
Node slow = head;
while (k - 1 > 0) {
if (fast.next != null) {
fast = fast.next;
k--;
} else {
return null;
}
}
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
/*5.合并两个有序单链表*/
public Node mergeTwoLists(Node headA, Node headB) {
if (headA == null) {
return headB;
}
if (headB == null) {
return headA;
}
Node node = new Node(-1);
Node cur = node;
while (headA != null && headB != null) {
if (headA.data < headB.data) {
cur.next = headA;
headA = headA.next;
cur = cur.next;
} else {
cur.next = headB;
headB = headB.next;
cur = cur.next;
}
if (headA != null) {
cur.next = headA;
}
if (headB != null) {
cur.next = headB;
}
}
return node.next;
}
/*6.以x为基准,将单链表分割成小于和大于x的两部分,小的在前,大的在后*/
public Node partition(Node head, int x) {
if (head == null) {
return null;
}
if (head.next == null) {
return head;
}
Node smallHead = new Node(-1);
Node smallTail = smallHead;
Node bigHead = new Node(-1);
Node bigTail = bigHead;
Node cur = head;
while (cur != null) {
if (cur.data < x) {
smallTail.next = cur;
smallTail = smallTail.next;
} else {
bigTail.next = cur;
bigTail = bigTail.next;
}
}
smallTail.next = bigHead.next;
return smallHead.next;
}
/*7.删除单链表中重复的结点*/
public Node deleteDuplication(Node head) {
Node newHead = new Node(-1);
Node newTail = newHead;
Node cur = head;
while (cur != null) {
if (cur.next != null && cur.data == cur.next.data) {
while (cur.next != null && cur.data == cur.next.data) {
cur = cur.next;
}
cur = cur.next;
} else {
newTail.next = cur;
newTail = newTail.next;
cur = cur.next;
}
}
return newHead.next;
}
/*8.链表的回文结构*/
public boolean chkPalindrome(Node head) {
if (head == null) {
return false;
}
if (head.next == null) {
return true;
}
//第一步:找单链表的中间结点
Node fast = head;
Node slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
//第二步:从中间结点往后开始反转剩余部分
Node p = slow.next;
while (p != null) {
Node next = p.next;
p.next = slow;
slow = p;
p = next;
if (p != null) {
next = p.next;
}
}
//第三步:比较两部分是否是完全相同的结点
while (head != slow) {
if (head.data != slow.data) {
return false;
}
if (head.next == slow) {
return true;
}
head = head.next;
slow = slow.next;
}
return true;
}
/*9.找两个单链表的第一个公共结点*/
public Node getIntersectionNode(Node headA, Node headB) {
int lenA = size(headA);
int lenB = size(headB);
if (lenA > lenB) {
int offset = lenA - lenB;
for (int i = 0; i < offset; i++) {
headA = headA.next;
}
} else {
int offset = lenB - lenA;
for (int i = 0; i < offset; i++) {
headB = headB.next;
}
}
while (headA != null && headB != null) {
if (headA == headB) {
return headA;
}
headA = headA.next;
headB = headB.next;
}
return null;
}
/*10.判断一个单链表是否有环*/
public boolean hasCycle(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;
}
/*11.返回链表开始入环的第一个结点(环的入口点)*/
public Node detectCycle(Node head) {
if (head == null) {
return null;
}
Node fast = head;
Node 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;
}
slow = head;
while (fast != head) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
/*获取链表的长度*/
private int size(Node head) {
int size = 0;
for (Node cur = head; cur != null; cur = cur.next) {
size++;
}
return size;
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)