//APPROACH - II
func isPalindromeUsingStack(l *list.List) bool {

	if l == nil {
		return false
	}
	st := stack.New()
	slow := l.Front()
	fast := l.Front()

	for fast != nil && fast.Next() != nil {
		st.Push(slow.Value.(int))
		slow = slow.Next()
		fast = fast.Next().Next()
	}

	//To ignore the middle element in case of odd length list
	if fast.Next() == nil {
		slow = slow.Next()
	}

	for slow != nil {
		m := st.Pop().(int)
		n := slow.Value.(int)
		if m != n {
			return false
		}
		slow = slow.Next()
	}
	return true
}

//Reverse list function
func reverseList(l *list.List) *list.List {
	m := list.New()

	for e := l.Front(); e != nil; e = e.Next() {
		m.PushFront(e.Value.(int))
	}
	return m
}

//Palinfrome function using reverse list approach - Iterative
func isPalindrome(l *list.List) bool {

	rev := reverseList(l)
	for e, f := l.Front(), rev.Front(); e != nil && f != nil; e, f = e.Next(), f.Next() {
		if e.Value.(int) != f.Value.(int) {
			return false
		}
	}
	return true
}

func removeDuplicate(l *list.List) *list.List {
	sMap = make(map[int]bool)
	var next *list.Element
	for e := l.Front(); e != nil; e = next {
		next = e.Next()
		m := e.Value.(int)
		//To verify whether the node value present in the map
		if sMap[m] == true {
			l.Remove(e)
		} else {
			sMap[m] = true
		}
	}
	return l
}

//Function to split the list around the value x
func splitAroundX(l *list.List, x int) *list.List {
	if l == nil {
		return nil
	}
	//Two lists for less than x and greater than X
	lThanX := list.New()
	gThanX := list.New()

	for e := l.Front(); e != nil; e = e.Next() {
		m := e.Value.(int)
		//Compare the value of x with the current node value and append to the respective list
		if m < x {
			lThanX.PushBack(m)
		} else {
			gThanX.PushBack(m)
		}
	}
	lThanX.PushBackList(gThanX)
	return lThanX
}

func removeDuplicate(l *list.List) *list.List {
	var next *list.Element
	var inNext *list.Element
	for e := l.Front(); e != nil; e = next {
		m := e.Value.(int)
		next = e.Next()
		//Inner for loop to iterate from the current node
		for f := e; f != nil; f = inNext {
			n := f.Value.(int)
			inNext = f.Next()
			if e != f {
				//To check whether the values m and n are same. If so, remove the node from the list
				if m == n {
					l.Remove(f)

				}
			}
		}
	}
	return l
}

//Function to add the list
func addLists(l *list.List, m *list.List) *list.List {
	if l == nil && m == nil {
		return nil
	}
	lLength := l.Len()
	mLength := m.Len()

	carry := 0
	value := 0
	resList := list.New()

	var e *list.Element
	var f *list.Element
	for e, f = l.Front(), m.Front(); e != nil && f != nil; e, f = e.Next(), f.Next() {
		value = carry + e.Value.(int) + f.Value.(int)
		//get the carry and value
		carry = 0
		carry = value / 10
		value = value % 10
		resList.PushFront(value)
	}
	//To identify the long list if the size is different
	var p *list.Element
	if lLength > mLength {
		p = e
	} else {
		p = f
	}
	for ; p != nil; p = p.Next() {
		value = carry + p.Value.(int)
		carry = 0
		carry = value / 10
		value = value % 10
		resList.PushFront(value)
	}
	if carry != 0 {
		resList.PushFront(carry)
	}
	return resList
}

//Iterative function to find the kth from last element
func findKFromLast(l *list.List, k int) *list.Element {
	size := l.Len()
	//Base condition. If the size of the list is less than k then kth element cannot be found
	if size < k {
		return nil
	}
	var elem *list.Element
	elem = l.Front()
	for i := 1; i < k; i++ {
		elem = elem.Next()
	}
	var first *list.Element
	for first = l.Front(); first != nil && elem != nil; elem, first = elem.Next(), first.Next() {
		//return the current node when current+k position is nil
		if elem.Next() == nil {
			return first
		}
	}
	return nil
}

func findLoopsInList(l *list.List) *list.Element {
	if l == nil {
		return nil
	}
	var head *list.Element
	var slow *list.Element
	var fast *list.Element

	head = l.Front()
	for slow, fast = l.Front(), l.Front(); slow != nil && fast != nil; slow, fast = slow.Next(), fast.Next().Next() {
		if slow == fast {
			break
		}
	}
	if fast == nil || fast.Next() == nil {
		return nil
	}
	slow = head
	for slow != fast {
		slow = slow.Next()
		fast = fast.Next()
	}
	return fast
}