您的位置:首页 > 教育 > 培训 > 数据结构(2):LinkedList和链表[2]

数据结构(2):LinkedList和链表[2]

2024/11/8 15:56:56 来源:https://blog.csdn.net/zh04101912138/article/details/142106388  浏览:    关键词:数据结构(2):LinkedList和链表[2]

我们在上一篇文章中着重讨论了单链表的实现。其中我们要注意单链表进行遍历时一步一步走的思想。那么这篇文章我们将继续讨论链表的更多内容,那就让我们开始吧。

1.经典单链表算法题

我们将通过几个经典的题对单链表进行进一步的认识。

(1)反转链表

206. 反转链表 - 力扣(LeetCode)

现在我们希望对链表进行反转。大致如下:

我们选择的方法,是遍历头插。举例子,我们现在用cur=head.next,即我们用cur引用2节点,我们把它进行头插,那么会变成下面这样。这里注意,我们原本的头节点在反转后,它的next为空,所以我们要先把头节点处理为空

那么我们发现,仅仅把头节点置为空它会找不到cur的下一个节点,我们需要再建立一个curNext引用来将他们连上,再将头节点变为“2”节点。

这个时候我们再把cur节点指向curNext,进行下一轮头插,直到所有节点都完成头插完成,因此我们可以想到这是一个循环,下面我们用代码实现一下:

 public Listnode reverseList(Listnode head) {//反转链表if(head==null||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)链表的中间节点

876. 链表的中间结点 - 力扣(LeetCode)

下面我们要寻找链表的中间节点,当链表节点数为偶数时,中间节点为中间第二个节点。我们的思想可以称之为“双指针”。我们定义两个节点fast和slow同时指向头节点,fast先走,一次走两步,slow在这之后一次走一步,当fast走完,slow正好在中间节点上

我们来实现一下:

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

(3)返回倒数第k个节点

面试题 02.02. 返回倒数第 k 个节点 - 力扣(LeetCode)

下面我们要找出倒数第k个节点,同样,我们也可以使用“双指针”的思想,我们这次先让fast先走k-1步,再让slow与它同步走,此时当fast走到最后时,slow恰好是倒数第k个,这个代码就很好实现了:

public int kthToLast(ListNode head, int k) {ListNode fast=head;ListNode slow=head;for(int i=0;i<k-1;i++){fast=fast.next;}while(fast.next!=null){fast=fast.next;slow=slow.next;}return slow.val;}

(4)合并两个有序链表

21. 合并两个有序链表 - 力扣(LeetCode)

下面我们要把两个有序链表合并成一个,同时合并出来的新链表也要保证有序。两个链表的头节点都给我们了,分别是list1和list2,我们要定义一个新的头节点nHead用来组建新的链表,然后用list1和list2进行比较,谁小,谁就先跟在nHead后面,同时自己往后走一步。这样就能串起来,一个链表串完了,剩下的就都是另一个链表的了,直接都穿上就可以了。

代码也很好实现:

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

(5)找出两个链表的第一个公共节点

160. 相交链表 - 力扣(LeetCode)

两个不等长的链表,我们要找出他们第一个公共节点,我们可以这么做。我们只需要让长的那个链表先走出两个链表长度的差值,这时他们就在同一起点,他们“齐步走”,就可以相遇了,如果一直没相遇,就说明没有公共节点。

那么我们需要先求出差值,再进行后续的操作,我们可以这样实现:

  public ListNode getIntersectionNode(ListNode headA, ListNode headB) {int pl=0;int ps=0;ListNode Pl=headA;ListNode Ps=headB;ListNode cur=new ListNode();cur=headA;while(cur!=null){cur=cur.next;pl++;}cur=headB;while(cur!=null){cur=cur.next;ps++;}int len=pl-ps;if(len<0){len=-len;Pl=headB;Ps=headA;}for(int i=0;i<len;i++){Pl=Pl.next;}while(Pl!=Ps){Pl=Pl.next;Ps=Ps.next;}return Pl;}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com