链表常见题|删除链表指定结点、反转链表、输出链表倒数第K个结点、判断回文、找到链表的相交结点、判断链表是否有环、找到链表入环结点

链表常见题

文章目录

链表常见题1.删除链表中等于给定值 **val** 的所有节点。2.反转一个单链表。3.给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。4.输入一个链表，输出该链表中倒数第k个结点。5.将两个有序链表合并为一个新的有序链表并返回。6.以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。7.在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。8.链表的回文结构。9.输入两个链表，找出它们相交的起始节点。10.给定一个链表，判断链表中是否有环。11.给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

不带头结点的单向链表

1.删除链表中等于给定值 val 的所有节点。

OJ链接

public static ListNode removeElements(ListNode head, int val) { if (head == null) { return head; } if (head.next == null) { if (head.val == val) { return null; } else { return head; } } ListNode cur = head; //1.当开始若干个结点等于给定值 while (cur.val == val) { cur = cur.next; } //2.当中间有结点等于给定值 head = cur; ListNode prev = head; while (prev != null) { if (prev.next != null && prev.next.val == val) { ListNode c = prev.next; //存在中间连续几个结点等于给定值的情况 while (c != null && c.val == val) { c = c.next; } //删除等于给定值的结点 prev.next = c; } prev = prev.next; } return head; }

2.反转一个单链表。

OJ链接

public static ListNode reverseList(ListNode head) { SingleLinkedList linkedList = new SingleLinkedList(); //1.空链表 if (head == null) { return head; } //2.只有一个节点 if (head.next == null) { return head; } //3.多节点 ListNode prev = null; ListNode cur = head; ListNode next; ListNode newHead = null; while (cur != null) { next = cur.next; if (cur.next == null) { newHead = cur; } cur.next = prev; prev = cur; cur = next; } return newHead; }

3.给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

OJ 链接

法一：遍历链表，得到链表的长度len，指针走len/2步，即可得到中间结点

法二：快慢指针，快指针走两步，慢指针走一步，当fast走到结尾时，slow指向的结点即为中间结点

//链表的中间节点 public static ListNode middleNode(ListNode head) { ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow; }

4.输入一个链表，输出该链表中倒数第k个结点。

OJ链接

快慢指针，快指针先走k步，再快慢指针同时走，当块指针走到结尾时，slow指向的结点即为指定结点

public static ListNode FindKthToTail(ListNode head,int k) { int len = size(head); //判断合法性 if (k < 0 || k > len) { return null; } ListNode fast = head; ListNode slow = head; //快指针先走k步 for (int i = 0; i < k; i++) { fast = fast.next; } while (fast != null ) { fast = fast.next; slow = slow.next; } return slow; }

5.将两个有序链表合并为一个新的有序链表并返回。

OJ链接

public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode cur1 = l1; ListNode cur2 = l2; //创建一个带头结点的链表 ListNode newHead = new ListNode(-1); ListNode newTail = newHead; while (cur1 != null && cur2 != null) { if (cur1.val < cur2.val) { newTail.next = new ListNode(cur1.val); newTail = newTail.next; //尾插 cur1 = cur1.next; } else { newTail.next = new ListNode(cur2.val); newTail = newTail.next; cur2 = cur2.next; } } if (cur1 != null) { while (cur1 != null) { newTail.next = new ListNode(cur1.val); newTail = newTail.next; cur1 = cur1.next; } } if (cur2 != null) { while (cur2 != null) { newTail.next = new ListNode(cur2.val); newTail = newTail.next; cur2 = cur2.next; } } return newHead.next; }

6.以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。

OJ链接

创建两个链表，一个链表连接大于x的结点，另一个链表连接小于x的结点，最后将两个链表连接即可

public ListNode partition(ListNode pHead, int x) { if (pHead == null) return null; if (pHead.next == null) return pHead; ListNode smallHead = new ListNode(-1); ListNode smallTail = smallHead; ListNode bigHead = new ListNode(-1); ListNode bigTail = bigHead; ListNode cur = pHead; while (cur != null) { if (cur.val < x) { smallTail.next = new ListNode(cur.val); smallTail = smallTail.next; }else{ bigTail.next = new ListNode(cur.val); bigTail = bigTail.next; } cur = cur.next; } smallTail.next = bigHead.next; return smallHead.next; }

7.在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。

OJ链接

创建新链表，当cur指向重复的点，循环后移，直至指向不重复的点，再将该点保存在新链表中

public ListNode deleteDuplication(ListNode pHead){ if (pHead == null) return null; if (pHead.next == null) return pHead; ListNode newHead = new ListNode(-1); ListNode newTail = newHead; ListNode cur = pHead; while (cur != null) { if (cur.next != null && cur.val == cur.next.val ) { //&&两边的操作不能调换，因为存在短路 while (cur.next != null && cur.val == cur.next.val) { cur = cur.next; } //cur再后移，指向不重复的结点 cur = cur.next; } else { newTail.next = new ListNode(cur.val); newTail = newTail.next; cur = cur.next; } } return newHead.next; }

8.链表的回文结构。

OJ链接

public boolean chkPalindrome(ListNode A){ //找到链表的中间结点 ListNode mid = midNode(A); //中间节点往后 反转 ListNode B = reverseList(mid); //比较 while (B != null) { if (A.val != B.val) { return false; } A = A.next; B = B.next; } return true; } //找到链表的中间结点 public ListNode midNode(ListNode head) { int length = 0; for (ListNode node = head; node != null; node = node.next) { length++; } int offset = length/2; for (int i = 0; i < offset; i++) { head = head.next; } return head; } //链表的反转 public ListNode reverseList(ListNode head) { if (head == null) return null; if (head.next == null) return head; ListNode prev = null; ListNode cur = head; ListNode pnext = cur.next; ListNode newHead = null; while (cur != null) { pnext = cur.next; if (pnext == null) { newHead = cur; } cur.next = prev; //刚开始prev是空 prev = cur; cur = pnext; } return newHead; }

9.输入两个链表，找出它们相交的起始节点。

OJ链接

得到两个链表的长度，先让较长的链表走差值的步数，两个链表同时走，若存在相同的节点，就是相交的起始结点

public ListNode getIntersectionNode(ListNode headA, ListNode headB) { int lenA = size(headA); int lenB = size(headB); int k = 0; int flg = 1; if (lenA>lenB) { k = lenA - lenB; } else { k = lenB - lenA; flg = 0; } if (flg == 1) { for (int i = 0; i < k; i++) { headA = headA.next; } } else { for (int i = 0; i < k; i++) { headB = headB.next; } } while (headA != null && headB != null) { if (headB == headA) { return headB; } headA = headA.next; headB = headB.next; } return null; } public static int size(ListNode head) { int len = 0; for (ListNode node = head; node != null; node = node.next) { len++; } return len; }

10.给定一个链表，判断链表中是否有环。

OJ链接

快慢指针，快指针走两步，慢指针走一步，（两指针速度差为1即可），当两指针重合时，链表有环

//判断链表是否有环 public static boolean hasCycle(ListNode head) { 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; }

11.给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

OJ链接

找到快慢指针重合的地方x，一个指针从头节点走，另一个结点从x走，当两指针重合即为入环的第一个结点

public ListNode detectCycle(ListNode head) { ListNode fast = head; ListNode slow = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if (fast == slow) { break; } } //不带环的情况 // fast == slow 不能证明链表带环，比如链表只有一个节点 if (fast == null || fast.next == null) { return null; } //cur 和 fast 同时走相同的步数 //循环条件：cur ！= fast，若一开始 cur = fast说明两者已在入环结点 ListNode cur = head; while (cur != fast) { cur = cur.next; fast = fast.next; } return cur; }