链表part02

链表的题目，如果涉及到对头节点的改动的话，就必须要用个哨兵节点dummy来执行头节点，不然不好多头节点进行移除或者换位的操作。
两两交换链表中的节点

/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */funcswapPairs(head*ListNode)*ListNode{dummy:=&ListNode{Next:head}pre:=dummyforhead!=nil&&head.Next!=nil{// 第一步由dummy位置指向2pre.Next=head.Next// 存储位置3nxt:=head.Next.Next// 第二步由位置2指向位置1head.Next.Next=head// 第三步由位置1指向位置3head.Next=nxt pre=head head=head.Next}returndummy.Next}

删除链表的倒数第N个节点
可以用双指针来做这道题，注意这里的位置问题，首先快指针，因为要从dummy开始走起，所以它要走n+1步，所以第一次循环更新fast的位置时，要让它从0遍历到n，这样待会slow和fast一起走的时候，当fast走到nil时，slow刚好走到倒数第n个数的前一个位置。

/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */funcremoveNthFromEnd(head*ListNode,nint)*ListNode{dummy:=&ListNode{Next:head}// 采用双指针slow,fast:=dummy,dummyfori:=0;i<=n;i++{// 注意i要 <= n,因为是从dummy开始走的// 所以要走n步slow待会才能走到删除节点的前一个位置fast=fast.Next}forfast!=nil{fast=fast.Next slow=slow.Next}slow.Next=slow.Next.Nextreturndummy.Next}

链表相交的位置
这道题可以一起遍历两条链表，如果两条链表的长度不一的话，可以把两条链表连起来遍历，比如说用 l1，l2分别指向两条链表headA，headB，当l1把headA遍历完之后，再指向headB继续遍历，当l2把headB遍历完之后，再指向headA继续遍历，这样最多O(2n)就能够找到相交的节点。

/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */funcgetIntersectionNode(headA,headB*ListNode)*ListNode{l1,l2:=headA,headBforl1!=l2{ifl1!=nil{l1=l1.Next}else{l1=headB}ifl2!=nil{l2=l2.Next}else{l2=headA}}returnl1}