链表常见简单算法

链表

type LinkNode struct{
    Val int
    Next *LinkNode
}

反转链表

func reverseLinkList(head *LinkNode)*LinkNode{
    curr:=head
    prev:=nil
    for curr.Next!=nil{
        next:=curr.Next
        curr.Next=prev
        prev=curr
        curr=next
    }
    return prev
}

输出链表倒数第K个节点值

func findKthFromEnd(head *LinkNode,k int)int{
    curr:=head
    count:=0
    goal:=head
    for curr.Next!=nil{
        curr=curr.Next
        if count<k{
            count++
        }else{
            goal=goal.Next
        }
    }
    if count<k{
        retrun nil
    }else{
        return goal.Val
    }
}

判断链表是否有环

// 判断链表是否有环
func hasCycle(head *ListNode) bool {
	if head == nil || head.Next == nil {
		return false
	}
	slow, fast := head, head.Next
	for slow != fast {
		if fast == nil || fast.Next == nil {
			return false
		}
		slow = slow.Next
		fast = fast.Next.Next
	}
	return true
}

两数相加 leetcode.2

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    // 定义sum用于计算链表当前位的值，carry为链表下一位的进位值
	var sum,carry int
    // 定义头尾两个链表指针，头指针用于记录返回链表头节点
    // 尾指针用于在链表尾部插入新节点
	var head,tail *ListNode
	for l1 != nil || l2 != nil {
        var(
            val1 int
            val2 int
        )
        newNode:=new(ListNode)
        if l1!=nil{
            val1 = l1.Val
            l1 = l1.Next
        }
        if l2!=nil{
            val2 = l2.Val
            l2 = l2.Next
        }
	    sum = val1 + val2 + carry
		sum, carry = sum%10, sum/10
        newNode.Val = sum
        // 记录头节点
        if head == nil{
            head = newNode
            tail = newNode
        }else{
		    tail.Next = newNode
		    tail = newNode
        }
	}
    if carry==1{
        tail.Next = &ListNode{Val:1}
    }
	return head
}