数据结构(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;}