链表
读题要仔细，只看题干，容易死的很惨。
设计链表
type node struct {
val int
next *node
}
type MyLinkedList struct {
size int
head , tail *node
}
/** Initialize your data structure here. */
func Constructor() MyLinkedList {
t := &node{}
h := &node{next: t}
return MyLinkedList{
head: h,
tail: t,
}
}
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
func (this *MyLinkedList) Get(index int) int {
if index < 0 || this.size <= index {
return -1
}
i , temp := 0 , this.head.next
for i < index {
i++
temp = temp.next
}
return temp.val
}
/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
func (this *MyLinkedList) AddAtHead(val int) {
temp := &node{val: val}
temp.next = this.head.next
this.head.next = temp
this.size++
}
/** Append a node of value val to the last element of the linked list. */
func (this *MyLinkedList) AddAtTail(val int) {
this.tail.val = val
temp := &node{}
this.tail.next = temp
this.tail = temp
this.size++
}
/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
func (this *MyLinkedList) AddAtIndex(index int, val int) {
if this.size < index {
return
} else if index <= 0 { //this part was check the discussion part , if index < 0 we will add at head.
this.AddAtHead(val)
return
} else if index == this.size {
this.AddAtTail(val)
return
}
i, temp := -1, this.head
for i+1 < index {
i++
temp = temp.next
}
nd := &node{val: val}
nd.next = temp.next
temp.next = nd
this.size++
}
/** Delete the index-th node in the linked list, if the index is valid. */
func (this *MyLinkedList) DeleteAtIndex(index int) {
if (index <0 || this.size <= index) {
return
}
i, temp := -1, this.head
for i + 1 < index {
i++
temp = temp.next
}
temp.next = temp.next.next
this.size--
}
/**
* Your MyLinkedList object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.Get(index);
* obj.AddAtHead(val);
* obj.AddAtTail(val);
* obj.AddAtIndex(index,val);
* obj.DeleteAtIndex(index);
*/
环形链表
一般环形链表使用快慢指针方式去做，快慢指针算法。
参看解释
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func hasCycle(head *ListNode) bool {
if head == nil {
return false
}
fast := head.Next
slow := head
for slow != nil && fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
if fast == slow {
return true
}
}
return false
}
环形链表II
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func detectCycle(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return nil
}
slow , fast := head.Next , head.Next.Next
//if has cycle finally slow == fast. then loop break.
//if don't have cycle finally fast.Next == nil . then loop break.
for fast != nil && fast.Next != nil && slow != fast {
slow , fast = slow.Next , fast.Next.Next
}
//no cycle.
if slow != fast {
return nil
}
//if has cycle , now the slow's position to the entrance will equal to the head to the entrance.
for slow != head {
slow, head = slow.Next, head.Next
}
return slow
}
相交链表
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func getIntersectionNode(headA, headB *ListNode) *ListNode {
//when the node catch up , the link list length is the same
a , b := headA , headB
lengthA , lengthB := 0 , 0
for a != nil {
a = a.Next
lengthA++
}
for b != nil {
b = b.Next
lengthB++
}
a , b = headA , headB
for lengthA < lengthB {
b = b.Next
lengthB--
}
for lengthA > lengthB {
a = a.Next
lengthA--
}
for a != b {
a = a.Next
b = b.Next
}
return a
}
删除链表的倒数第N个节点
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func removeNthFromEnd(head *ListNode, n int) *ListNode {
//keep fast and slow in n distance , when fast get the end of the list , slow is in the position
fast := head
slow := head
for i := 0 ;i < n ; i++ {
if fast.Next != nil {
fast = fast.Next
} else {
//for the first value.
return head.Next
}
}
for fast.Next != nil {
fast = fast.Next
slow = slow.Next
}
slow.Next = slow.Next.Next
return head
}
反转链表
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseList(head *ListNode) *ListNode {
var newHead ListNode
for head != nil {
newHead.Next, head.Next, head = head, newHead.Next, head.Next
}
return newHead.Next
}
移除链表元素
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func removeElements(head *ListNode, val int) *ListNode {
if head == nil {
return head
}
var orig ListNode
orig.Next = head
temp := &orig
for head != nil {
if head.Val == val {
temp.Next , head = head.Next , head.Next
} else {
temp , head = head , head.Next
}
}
return orig.Next
}
回文链表
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func isPalindrome(head *ListNode) bool {
if head == nil || head.Next == nil {
return true
}
fast, slow, tmp := head, head, head
var l ListNode
for fast != nil && fast.Next != nil {
fast = fast.Next.Next
tmp = slow.Next
slow.Next = l.Next
l.Next = slow
slow = tmp
}
if fast != nil {
slow = slow.Next
}
tmp = l.Next
for slow != nil && tmp != nil && slow.Val == tmp.Val {
slow, tmp = slow.Next, tmp.Next
}
return slow == nil
}
合并两个有序链表
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
if l1 == nil {
return l2
}
if l2 == nil {
return l1
}
if l1.Val < l2.Val {
l1.Next = mergeTwoLists(l1.Next, l2)
return l1
} else {
l2.Next = mergeTwoLists(l1, l2.Next)
return l2
}
}
旋转链表
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func rotateRight(head *ListNode, k int) *ListNode {
if head == nil || head.Next == nil || k == 0 {
return head
}
len := 1
tail := head
for tail.Next != nil {
tail = tail.Next
len++
}
tail.Next = head //become a cycle
k = k % len //we made this a cycle , so we don't need this to round more than 1 time
for i := 0; i < len-k; i++ {
tail = tail.Next
}
head = tail.Next
tail.Next = nil
return head
}
网友评论