链表必刷题之一

本文主要是介绍链表必刷题之一，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

public ListNode reverseList(ListNode head) {if(head == null) {return null;}if(head.next == null) {return head;}//两个节点以上ListNode cur = head.next;head.next = null;while(cur!=null){ListNode curNext = cur.next;cur.next = head;head = cur;cur = curNext;}return head;}

图解：

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

public ListNode middleNode(ListNode head) {if(head.next == null) {return head;}ListNode fast = head;ListNode slow = head;while(fast!=null&&fast.next!=null) {fast = fast.next.next;slow = slow.next;}return slow;}

图解：定义快慢指针，快指针走慢指针的二倍，当快指针走完时，慢指针走到一半，即慢指针指向中间节点。

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

public ListNode FindKthToTail(ListNode head,int k) {if(k<=0||head==null) {return null;}ListNode fast = head;ListNode slow = head;int count1 = 0;while(fast.next!=null){fast = fast.next;if(count1 >= k-1){slow = slow.next;}count1++;}if(count1 < k-1){return null;}return slow;}

 图解：快指针先走k-1步，然后快慢指针一起走，当快指针走完时，慢指针指向倒数第k个节点。

 4.将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode newNode = new ListNode(0);ListNode temp = newNode;while(list1!=null&&list2!=null){if(list1.val< list2.val){temp.next = list1;temp = temp.next;list1 = list1.next;}else{temp.next = list2;temp = temp.next;list2 = list2.next;}}if(list1!=null){temp.next = list1;}if(list2!=null){temp.next = list2;}return newNode.next;}

图解：定义虚拟节点，通过不断比较将小节点通过尾插法连接虚拟节点后，最后返回虚拟节点的next。

 

这篇关于链表必刷题之一的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---