leetcode链表相关

206 翻转链表

代码：

func reverseList(head *ListNode) *ListNode {
    var dummy *ListNode
    for head != nil{
        temp := head.Next
        head.Next = dummy
        dummy = head
        head = temp
    }
    return dummy
}

思路：

1. 后一个节点指向前一个节点，需要用到的东西
   1. 前一个节点的指针
   2. 记录当前指针，以备下一个节点使用和位移一步
2. 全部反转，第一个节点需要指向nil节点，开始时需要构造一个空节点

876.链表的中间节点

代码：

func middleNode(head *ListNode) *ListNode {
    fast,slow := head,head
    for fast != nil && fast.Next != nil{
        slow = slow.Next
        fast = fast.Next.Next
    }
    return slow
}

思路：

1. 快慢指针为链表第一解决思路
2. 中间节点，意味两倍的关系

160.相交链表

代码：

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    i := headA
    j := headB
    for i != j {
        if i == nil{
            i = headB
        }else{
            i = i.Next
        }
        if j == nil{
            j = headA
        }else{
            j = j.Next
        }
    }
    return i
}

思路：

1. A 和 B沿着到终点，遇到nil，到对方的跑道继续前进，最终会相遇；因为A走过的全部加B的路是相等的

141.环形链表

代码：

func hasCycle(head *ListNode) bool {
    if head == nil{
        return false
    }
    for i,j:=head,head.Next;j != nil && j.Next != nil;i,j = i.Next,j.Next.Next{
        if i == j{
            return true
        }
    }
    return false
}

思路：

1. 快慢指针，当两者相遇时，说明有环
2. 循环条件为快指针是否为空，和快指针的Next是否为空。因为代码中快指针需要Next.Next

92.反转链表二

代码：

func reverse(head *ListNode)*ListNode{
    var dummy *ListNode
    for head != nil{
        temp := head.Next
        head.Next = dummy
        dummy = head
        head = temp
    }
    return dummy
}

func reverseBetween(head *ListNode, left int, right int) *ListNode {
    dummy := &ListNode{
        Next:head,
    }
    pre := dummy
    // 反转前一个节点
    for i:=0;i<left-1;i++{
        pre = pre.Next
    }
    rightNode := pre 
    // 反转区间的最后一个节点
    for j:=0;j<right-left+1;j++{
        rightNode = rightNode.Next
    }
    // 记录另两个有用的节点
    curr := rightNode.Next
    leftNode := pre.Next

    // 掐断连接，给反转函数干净的链表
    rightNode.Next = nil
    pre.Next = nil

    // 反转部分链表
    reverse(leftNode)

    // 拼接反转部分
    pre.Next = rightNode
    leftNode.Next = curr

    return dummy.Next

}

思路：

1. 构造哑结点可以避免讨论
2. 一共需记录四个节点，区间的首尾节点和区间外相邻的两个节点
3. 将这部分依次反转
4. 反转完开始拼接

328.奇偶链表

代码：

func oddEvenList(head *ListNode) *ListNode {
	if head == nil{
		return head
	}
	odd := head
	even := head.Next
	originEvenHead := head.Next
	for even != nil && even.Next != nil {
		odd.Next = even.Next
		odd = odd.Next
		even.Next = odd.Next
		even = even.Next
	}
	
	odd.Next = originEvenHead
	
	return head
}

思路：

1. 不用dummy node，因为偶链表需要拼接在奇链表后，需要以偶链表作为判空条件
2. 最后偶链表判空，循环退出时，奇链表永远是非空的，所以可以直接赋值
3. 不加哑结点，需要判断头结点是否为空