大佬教程收集整理的这篇文章主要介绍了链表笔试题总结——1，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
最近在复习数据结构，做了一些数据结构方面的笔试编程题，代码总结如下：
ps：下面的单链表默认都没有傀儡节点。
1、删除链表中等于给定值 val 的所有节点
1 public ListNode removeElements(ListNode head, int val) { 2 ListNode newhead = head; 3 while (newhead != null && newhead.val == val) { 4 newhead = newhead.next; 5 } 6 if (newhead == null) 7 return null; 8 ListNode front = newhead; 9 ListNode last = newhead.next; 10 while (last != null) { 11 if (last.val == val) { 12 front.next = last.next; 13 last = last.next; 14 } else { 15 front = last; 16 last = last.next; 17 } 18 } 19 return newhead; 20 }
2、反转一个单链表
1 public ListNode reverseList(ListNode head) { 2 if (head == null) { 3 return null; 4 } 5 ListNode newHead = head; 6 ListNode tmp = head.next; 7 head.next = null; 8 while (tmp != null) { 9 ListNode temp = tmp; 10 tmp = tmp.next; 11 temp.next = newHead; 12 newHead = temp; 13 } 14 return newHead; 15 }
3、求链表的中间节点
1 public ListNode middleNode(ListNode head) { 2 if (head == null) { 3 return null; 4 } 5 if (head.next == null) { 6 return head; 7 } 8 int length = 0; 9 ListNode tmp = head; 10 while (tmp != null) { 11 length++; 12 tmp = tmp.next; 13 } 14 tmp = head; 15 for (int i = 0; i < length / 2; i++) { 16 tmp = tmp.next; 17 } 18 return tmp; 19 }
4、求倒数第k个链表
1 public ListNode FindKth@R_647_10586@il(ListNode head, int k) { 2 if (k == 0) { 3 return null; 4 } 5 ListNode front = head; 6 ListNode last = head; 7 while (--k > 0 && last != null) { 8 last = last.next; 9 } 10 if (last == null) { 11 return null; 12 } 13 if (last.next == null && k == 0) { 14 return head; 15 } 16 17 while (last.next != null) { 18 front = front.next; 19 last = last.next; 20 } 21 return front; 22 }
5、分割链表
1 public ListNode partition(ListNode pHead, int X) { 2 if (pHead == null) { 3 return null; 4 } 5 ListNode newHead = null; 6 ListNode tmp = pHead; 7 ListNode temp = newHead; 8 while (pHead != null) { 9 if (pHead.val < X) { 10 if (newHead == null) { 11 newHead = pHead; 12 temp = newHead; 13 } else { 14 temp.next = pHead; 15 temp = temp.next; 16 } 17 pHead = pHead.next; 18 temp.next = null; 19 } else { 20 break; 21 } 22 } 23 if (pHead == null) { 24 return newHead; 25 } 26 27 if (newHead == null) { 28 while (tmp.next != null && tmp.next.val >= X) { 29 tmp = tmp.next; 30 } 31 if (tmp.next == null) { 32 return pHead; 33 } 34 newHead = tmp.next; 35 tmp.next = tmp.next.next; 36 temp = newHead; 37 temp.next = null; 38 } 39 40 tmp = pHead; 41 while (tmp.next != null) { 42 while (tmp.next != null && tmp.next.val >= X) { 43 tmp = tmp.next; 44 } 45 if (tmp.next == null) { 46 temp.next = pHead; 47 } else { 48 temp.next = tmp.next; 49 temp = temp.next; 50 tmp.next = tmp.next.next; 51 temp.next = null; 52 } 53 } 54 55 temp.next = pHead; 56 return newHead; 57 }
6、去除链表重复节点，即1122234变成34
1 public ListNode deleteDuplication(ListNode pHead) { 2 if (pHead == null) { 3 return null; 4 } 5 // 去除开头重复节点 6 while (pHead.next != null && pHead.val == pHead.next.val) { 7 int tmp = pHead.val; 8 while (pHead != null && pHead.val == tmp) { 9 pHead = pHead.next; 10 } 11 if (pHead == null) { 12 return null; 13 } 14 } 15 if (pHead.next == null) { 16 return pHead; 17 } 18 // 去除中间重复节点 19 Boolean is = false; 20 ListNode node = pHead; 21 while (node.next != null) { 22 ListNode temp = node.next; 23 int tmp = temp.val; 24 while (temp.next != null && temp.next.val == temp.val) { 25 temp.next = temp.next.next; 26 is = true; 27 } 28 if (is) { 29 node.next = temp.next; 30 is = false; 31 } else { 32 node = node.next; 33 } 34 } 35 return pHead; 36 }
7、判断链表的回文结构
1 public Boolean chkPalindrome(ListNode A) { 2 ArrayList<Integer> list = new ArrayList<>(); 3 ListNode cur = A; 4 while (cur != null) { 5 list.add(cur.val); 6 cur = cur.next; 7 } 8 int length = list.size(); 9 int left = 0; 10 int right = length - 1; 11 while (left < right) { 12 if (!list.get(left).equals(list.get(right))) { 13 return false; 14 } 15 left++; 16 right--; 17 } 18 return true; 19 }
8、判断两个链表是否有交点，并返回第一个交点
public ListNode geTintersectionNode(ListNode headA, ListNode headB) { int lengthA = 0; int lengthB = 0; ListNode tmpA = headA; ListNode tmpB = headB; while (tmpA != null) { lengthA++; tmpA = tmpA.next; } while (tmpB != null) { lengthB++; tmpB = tmpB.next; } tmpA = headA; tmpB = headB; if (lengthA > lengthB) { for (int i = 0; i < lengthA - lengthB; i++) { tmpA = tmpA.next; } } else { for (int i = 0; i < lengthB - lengthA; i++) { tmpB = tmpB.next; } } while (tmpA != null) { if (tmpA == tmpB) { return tmpA; } tmpA = tmpA.next; tmpB = tmpB.next; } return null; }
9、判断链表是否有环
1 public Boolean hasCycle(ListNode head) { 2 ListNode slow = head; 3 ListNode fast = head; 4 while (fast != null && fast.next != null) { 5 fast = fast.next.next; 6 slow = slow.next; 7 if (fast == slow) { 8 return true; 9 } 10 } 11 return false; 12 }
10、找链表的入环节点
1 public ListNode detectCycle(ListNode head) { 2 // 判断是否有环 3 ListNode slow = head; 4 ListNode fast = head; 5 while (fast != null && fast.next != null) { 6 slow = slow.next; 7 fast = fast.next.next; 8 if (fast == slow) { 9 break; 10 } 11 } 12 if (fast == null || fast.next == null) { 13 return null; 14 } 15 // 找入环结点 16 slow = head; 17 while (slow != fast) { 18 slow = slow.next; 19 fast = fast.next; 20 } 21 return slow; 22 }
11、删除倒数第n个节点
1 public ListNode removeNthFromEnd(ListNode head, int n) { 2 ListNode fast = head; 3 ListNode slow = head; 4 int i = 0; 5 for (; i < n && fast != null; i++) { 6 fast = fast.next; 7 } 8 if (i == n) { 9 if (fast == null) { 10 head = head.next; 11 return head; 12 } else { 13 while (fast.next != null) { 14 slow = slow.next; 15 fast = fast.next; 16 } 17 slow.next = slow.next.next; 18 return head; 19 } 20 } 21 return head; 22 }
12、合并k个有序链表
1 public ListNode mergeKLists(ListNode[] lists) { 2 int size = lists.length; 3 if (size == 0) { 4 return null; 5 } 6 if (size == 1) { 7 return lists[0]; 8 } 9 ListNode tt = lists[0]; 10 for (int i = 1; i < size; i++) { 11 ListNode tmp = lists[i]; 12 tt = lists[0]; 13 // 合并两个链表 14 if (tt == null) { 15 lists[0] = tmp; 16 conTinue; 17 } 18 if (tmp == null) { 19 conTinue; 20 } 21 // 判断第一个结点的大小 22 if (tmp.val < lists[0].val) { 23 lists[0] = tmp; 24 tmp = tmp.next; 25 lists[0].next = tt; 26 tt = lists[0]; 27 } 28 while (tt.next != null && tmp != null) { 29 if (tt.next.val >= tmp.val) { // 插入tmp 30 ListNode t = tmp.next; 31 tmp.next = tt.next; 32 tt.next = tmp; 33 tmp = t; 34 tt = tt.next; 35 } else { 36 tt = tt.next; 37 } 38 } 39 if (tt.next == null) { 40 tt.next = tmp; 41 } 42 } 43 return lists[0]; 44 }
13、两两交换链表中的节点
1 public ListNode swapPairs(ListNode head) { 2 if (head == null) { 3 return null; 4 } 5 if (head.next == null) { 6 return head; 7 } 8 ListNode tmp = head; // 1 9 ListNode front = head; // 1 10 head = head.next; // 2 11 tmp.next = head.next;// 1->3 12 head.next = tmp;// 2->1 13 tmp = front.next;// 3 14 while (tmp != null && tmp.next != null) { 15 ListNode t = tmp.next.next;// null 16 front.next = tmp.next; 17 tmp.next.next = tmp; 18 tmp.next = t; 19 front = tmp; 20 tmp = t; 21 } 22 return head; 23 }
14、旋转链表，顺时针旋转k个位置，即12345，旋转2个位置后变成45123
1 public ListNode rotateRight(ListNode head, int k) { 2 if (head == null) { 3 return null; 4 } 5 if (head.next == null) { 6 return head; 7 } 8 int length = 0; 9 ListNode fast = head; 10 ListNode slow = head; 11 // 计算链表长度 12 while (fast != null) { 13 fast = fast.next; 14 length++; 15 } 16 int len = k % length; // 旋转长度 17 if (len == 0) { 18 return head; 19 } 20 fast = head; 21 for (int i = 0; i < len; i++) { 22 fast = fast.next; 23 } 24 while (fast.next != null) { 25 slow = slow.next; 26 fast = fast.next; 27 } 28 fast.next = head; 29 head = slow.next; 30 slow.next = null; 31 return head; 32 }
15、排序链表
1 public ListNode sortList(ListNode head) { 2 if (head == null || head.next == null) { 3 return head; 4 } 5 ListNode tail = head; 6 ListNode tmp = head; 7 ListNode cur = head.next; 8 while (cur != null) { 9 tmp = head; 10 if (cur.val >= tail.val) { // 尾插 11 tail = cur; 12 cur = cur.next; 13 conTinue; 14 } 15 if (cur.val < head.val) { // 头插 16 tail.next = cur.next; 17 cur.next = head; 18 head = cur; 19 cur = tail.next; 20 conTinue; 21 } 22 while (tmp != tail && tmp.next.val < cur.val) { 23 tmp = tmp.next; 24 } 25 tail.next = cur.next; 26 cur.next = tmp.next; 27 tmp.next = cur; 28 cur = tail.next; 29 } 30 return head; 31 }
16、重排链表
1 public void reorderList(ListNode head) { 2 if (head == null || head.next == null || head.next.next == null) { 3 return; 4 } 5 int length = 0; 6 ListNode slow = head; 7 ListNode fast = head; 8 while (fast.next != null && fast.next.next != null) { 9 slow = slow.next; 10 fast = fast.next.next; 11 } 12 ListNode lasthead = slow.next; // 指向后半部分链表【待逆置的链表】 13 slow.next = null; 14 // 逆置后半部分链表 15 fast = lasthead.next; 16 ListNode tmp = fast; 17 lasthead.next = null; 18 while (fast != null) { 19 tmp = fast.next; 20 fast.next = lasthead; 21 lasthead = fast; 22 fast = tmp; 23 } 24 // 合并两个链表 25 fast = lasthead.next; 26 slow = head; 27 while (lasthead != null && slow != null) { 28 fast = lasthead.next; 29 lasthead.next = slow.next; 30 slow.next = lasthead; 31 lasthead = fast; 32 slow = slow.next.next; 33 } 34 }
以上是部分链表编程题，后续我还会放置更多的编程题及其答案，上述代码有什么不对的地方或者可以优化的地方，欢迎大家指出~~
以上是大佬教程为你收集整理的链表笔试题总结——1全部内容，希望文章能够帮你解决链表笔试题总结——1所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。